Computer Science – Formal Languages and Automata Theory
Scientific paper
2011-01-21
Computer Science
Formal Languages and Automata Theory
Presented at LICS 2011
Scientific paper
Over finite words, languages of dot-depth one are expressively complete for alternation-free first-order logic. This fragment is also known as the Boolean closure of existential first-order logic. Here, the atomic formulas comprise order, successor, minimum, and maximum predicates. Knast (1983) has shown that it is decidable whether a language has dot-depth one. We extend Knast's result to infinite words. In particular, we describe the class of languages definable in alternation-free first-order logic over infinite words, and we give an effective characterization of this fragment. This characterization has two components. The first component is identical to Knast's algebraic property for finite words and the second component is a topological property, namely being a Boolean combination of Cantor sets. As an intermediate step we consider finite and infinite words simultaneously. We then obtain the results for infinite words as well as for finite words as special cases. In particular, we give a new proof of Knast's Theorem on languages of dot-depth one over finite words.
Kufleitner Manfred
Lauser Alexander
No associations
LandOfFree
Languages of Dot-depth One over Infinite Words 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 Languages of Dot-depth One over Infinite Words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Languages of Dot-depth One over Infinite Words will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-19368