The Taub Faculty of Computer Science Events and Talks

In this talk we show how logic can be eliminated from several meta-theorems relating the definability of graph parameters in sublogics of Second Order Logic to their computational complexity over certain graph classes.

A famous example of such a meta-theorem is Courcelle's theorem, stating that graph parameters definable in Monadic Second Order Logic are computable in polynomial time over graph classes of bounded tree-width. A logic-free version of this theorem was proved by Lovasz in 2007. Other examples include the generalization of Courcelle's theorem to bounded clique-width by Courcelle, Makowsky, and Rotics, and a further generalized meta-theorem involving sum-like inductive graph classes, by Makowsky.

We will eliminate logic from these theorems by replacing their definability conditions with finiteness conditions on Hankel matrices. A Hankel matrix $H(f, \Box)$ of a graph parameter $f$ with a binary operation $\Box$ on graphs is an infinite matrix whose rows and columns are indexed by graphs, where the entry $H(f,\Box)_{G_1,G_2}$ is given by: $H(f,\Box)_{G_1,G_2} = f(G_1 \Box G_2)$. A special case in our treatment will include a characterization of the word functions recognizable by weighted automata.

Finally, we will discuss questions raised by the fact that there are uncountably many graph parameters satisfying our finiteness conditions, while only countably many graph parameters are definable.

Joint work with Johann Makowsky.