On the logical definability of centrain graph and poset languages
Pascal Weil · Journal of automata, languages and combinatorics · 2004
We show that it is equivalent, for certain sets of finite graphs, to be definable in CMS (counting monadic second-order logic, a natural extension of monadic second-order logic), and to be recognizable in an algebraic framework induced by the notion of modular decomposition of a finite graph. More precisely, we consider the set F ∞ of composition operations on graphs which occur in the modular decomposition of finite graphs. If F is a subset of F ∞ we say that a graph is an F-graph if it can be decomposed using only operations in F. A set of F-graphs is recognizable if it is a union of classes in a finite-index equivalence relation which is preserved by the operations in F. We show that if F is finite and its elements enjoy only a limited amount of commutativity-a property which we call weak rigidity, then recognizability is equivalent to CMS-definability. This requirement is weak enough to be satisfied whenever all F-graphs are posets, that is, transitive dags. In particular, our result generalizes Kuske's recent result on series-parallel poset languages.