Eliminating Logic from Meta Theorems

A meta theorem, in our context, is a statement about a logic L of the form: ``If a graph parameter f is definable in L, then it is computable in polynomial time over graph classes of a certain kind. '' A famous example is Courcelle’s theorem, which states that the definability of graph properties in Monadic Second Order Logic implies they are linear time computable over graph classes of bounded tree-width. In 1998 the theorem was generalized to graph parameters and graph classes of bounded clique-width by Courcelle, Makowsky, and Rotics. In 2004, J. A. Makowsky gave a further generalized meta theorem involving sum-like inductive graph classes, which are inductively defined using a finite set of basic graphs and a finite set of binary sum-like operations. We eliminate logic from these meta theorems by replacing their definability conditions with finiteness conditions on Hankel matrices. A Hankel matrix H(f, \Box) for a graph parameter f and a binary operation \Box on graphs is an infinite matrix where the rows and columns are labeled with graphs, and the entry corresponding to the row labeled with G and the column labeled with G' is given by the value f(G \Box G'). We show that the graph parameters covered by our logic-free treatment are a proper superset of the graph parameters covered by the meta theorems involving logic. Joint work with J. A. Makowsky.

Authors

• Nadia Labai Faculty of Computer Science, Technion-IIT, Haifa, Israel

Keywords

No keywords are indexed for this paper.