On the logical definability of certain graph and poset languages
<|reference_start|>On the logical definability of certain graph and poset languages: 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\_\infty$ of composition operations on graphs which occur in the modular decomposition of finite graphs. If $F$ is a subset of $F\_{\infty}$, we say that a graph is an $\calF$-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.<|reference_end|>
@article{weil2006on,
    title={On the logical definability of certain graph and poset languages},
    author={Pascal Weil (LaBRI)},
    journal={Journal of Automata, Languages and Computation 9 (2004) 147-165},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0609048},
    primaryClass={cs.LO}
}