Computer Science – Formal Languages and Automata Theory
Scientific paper
2011-10-06
Computer Science
Formal Languages and Automata Theory
21 pages
Scientific paper
We introduce an automata model for data words, that is words that carry at each position a symbol from a finite alphabet and a value from an unbounded data domain. The model is (semantically) a restriction of data automata, introduced by Bojanczyk, et. al. in 2006, therefore it is called weak data automata. It is strictly less expressive than data automata and the expressive power is incomparable with register automata. The expressive power of weak data automata corresponds exactly to existential monadic second order logic with successor +1 and data value equality \sim, EMSO2(+1,\sim). It follows from previous work, David, et. al. in 2010, that the nonemptiness problem for weak data automata can be decided in 2-NEXPTIME. Furthermore, we study weak B\"uchi automata on data omega-strings. They can be characterized by the extension of EMSO2(+1,\sim) with existential quantifiers for infinite sets. Finally, the same complexity bound for its nonemptiness problem is established by a nondeterministic polynomial time reduction to the nonemptiness problem of weak data automata.
Kara Ahmet
Schwentick Thomas
Tan Tony
No associations
LandOfFree
Feasible Automata for Two-Variable Logic with Successor on Data 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 Feasible Automata for Two-Variable Logic with Successor on Data Words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Feasible Automata for Two-Variable Logic with Successor on Data Words will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-181348