First-order Fragments with Successor over Infinite WordsReport as inadecuate




First-order Fragments with Successor over Infinite Words - Download this document for free, or read online. Document in PDF available to download.

1 ENS Cachan - École normale supérieure - Cachan 2 University of Stuttgart

Abstract : We consider fragments of first-order logic and as models we allow finite and infinite words simultaneously. The only binary relations apart from equality are order comparison \lt and the successor predicate $+1$. We give characterizations of the fragments $\Sigma 2 = \Sigma 2\lt,\suc$ and $\FO^2 = \FO^2\lt,\suc$ in terms of algebraic and topological properties. To this end we introduce the factor topology over infinite words. It turns out that a language $L$ is in $\FO^2 \cap \Sigma 2$ if and only if $L$ is the interior of an $\FO^2$ language. Symmetrically, a language is in $\FO^2 \cap \Pi 2$ if and only if it is the topological closure of an $\FO^2$ language. The fragment $\Delta 2 = \Sigma 2 \cap \Pi 2$ contains exactly the clopen languages in $\FO^2$. In particular, over infinite words $\Delta 2$ is a strict subclass of $\FO^2$. Our characterizations yield decidability of the membership problem for all these fragments over finite and infinite words; and as a corollary we also obtain decidability for infinite words. Moreover, we give a new decidable algebraic characterization of dot-depth 3-2 over finite words. Decidability of dot-depth 3-2 over finite words was first shown by Gla{ß}er and Schmitz in STACS 2000, and decidability of the membership problem for $\FO^2$ over infinite words was shown 1998 by Wilke in his habilitation thesis whereas decidability of $\Sigma 2$ over infinite words is new.

Keywords : infinite words regular languages first-order logic automata theory semigroups topology





Author: Jakub Kallas - Manfred Kufleitner - Alexander Lauser -

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



DOWNLOAD PDF




Related documents