Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2695
Authors: Kallas, Jakub
Kufleitner, Manfred
Lauser, Alexander
Title: First-order fragments with successor over infinite words
Issue Date: 2010
metadata.ubs.publikation.typ: Arbeitspapier
Series/Report no.: Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2010,8
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-60273
http://elib.uni-stuttgart.de/handle/11682/2712
http://dx.doi.org/10.18419/opus-2695
Abstract: We consider fragments of first-order logic and as models we allow finite andinfinite words simultaneously. The only binary relations apart from equalityare order comparison < and the successor predicate +1. We givecharacterizations of the fragments Sigma2 = Sigma2[<,+1] and FO2 = FO2[<,+1] interms of algebraic and topological properties. To this end we introduce thefactor topology over infinite words. It turns out that a language L is in theintersection of FO2 and Sigma2 if and only if L is the interior of an FO2language. Symmetrically, a language is in the intersection of FO2 and Pi2 ifand only if it is the topological closure of an FO2 language. The fragmentDelta2, which by definition is the intersection Sigma2 and Pi2 contains exactlythe clopen languages in FO2. In particular, over infinite words Delta2 is astrict subclass of FO2. Our characterizations yield decidability of themembership problem for all these fragments over finite and infinite words; andas a corollary we also obtain decidability for infinite words. Moreover, wegive a new decidable algebraic characterization of dot-depth 3/2 over finitewords. Decidability of dot-depth 3/2 over finite words was first shown by Glaßer andSchmitz in STACS 2000, and decidability of the membership problem for FO2 overinfinite words was shown 1998 by Wilke in his habilitation thesis whereasdecidability of Sigma2 over infinite words was not known before.
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
TR_2010_08.pdf425,13 kBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.