Computer Science – Logic in Computer Science
Scientific paper
2006-09-11
Journal of Automata, Languages and Computation 9 (2004) 147-165
Computer Science
Logic in Computer Science
Scientific paper
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.
No associations
LandOfFree
On the logical definability of certain graph and poset languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the logical definability of certain graph and poset languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the logical definability of certain graph and poset languages will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-25454