On the logical definability of certain graph and poset languagesReportar como inadecuado

On the logical definability of certain graph and poset languages - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LaBRI - Laboratoire Bordelais de Recherche en Informatique

Abstract : 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.

keyword : graph languages logical definability algebraic recognizability

Autor: Pascal Weil -

Fuente: https://hal.archives-ouvertes.fr/


Documentos relacionados