Computer Science – Formal Languages and Automata Theory
Scientific paper
2010-06-14
Computer Science
Formal Languages and Automata Theory
The results of this paper were presented at CIAA 2010; University of Stuttgart, Computer Science
Scientific paper
We introduce partially ordered two-way B\"uchi automata and characterize their expressive power in terms of fragments of first-order logic FO[<]. Partially ordered two-way B\"uchi automata are B\"uchi automata which can change the direction in which the input is processed with the constraint that whenever a state is left, it is never re-entered again. Nondeterministic partially ordered two-way B\"uchi automata coincide with the first-order fragment Sigma2. Our main contribution is that deterministic partially ordered two-way B\"uchi automata are expressively complete for the first-order fragment Delta2. As an intermediate step, we show that deterministic partially ordered two-way B\"uchi automata are effectively closed under Boolean operations. A small model property yields coNP-completeness of the emptiness problem and the inclusion problem for deterministic partially ordered two-way B\"uchi automata.
Kufleitner Manfred
Lauser Alexander
No associations
LandOfFree
Partially Ordered Two-way Büchi Automata 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 Partially Ordered Two-way Büchi Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Partially Ordered Two-way Büchi Automata will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-422592