On the logical definability of certain graph and poset languages
| dc.creator | Weil, Pascal | |
| dc.date | 2006-09-11 | |
| dc.date.accessioned | 2026-07-07T07:23:50Z | |
| dc.date.available | 2026-07-07T07:23:50Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/cs/0609048 | |
| dc.identifier | http://arxiv.org/abs/cs/0609048 | |
| dc.identifier | Journal of Automata, Languages and Computation 9 (2004) 147-165 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/116128 | |
| dc.subject | Logic in Computer Science | |
| dc.title | On the logical definability of certain graph and poset languages | |
| dc.type | text |