On Counting Graphs for Modal Logic with Counting

Avijeet Ghosh, François Schwarzentruber

In this paper, we study the theoretical computational complexity of counting trees and graphs that are classified positively by a graph neural networks, or said equivalently that satisfy a given formula of modal logic with counting. We also study convergence.