Computer Science – Formal Languages and Automata Theory
Scientific paper
2009-10-30
Computer Science
Formal Languages and Automata Theory
An extended abstract of this work has been published in the proceedings of the 34th International Symposium on Mathematical Fo
Scientific paper
In this paper we study a subclass of pebble automata (PA) for data languages for which the emptiness problem is decidable. Namely, we introduce the so-called top view weak PA. Roughly speaking, top view weak PA are weak PA where the equality test is performed only between the data values seen by the two most recently placed pebbles. The emptiness problem for this model is decidable. We also show that it is robust: alternating, nondeterministic and deterministic top view weak PA have the same recognition power. Moreover, this model is strong enough to accept all data languages expressible in Linear Temporal Logic with the future-time operators, augmented with one register freeze quantifier.
No associations
LandOfFree
On Pebble Automata for Data Languages with Decidable Emptiness Problem 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 On Pebble Automata for Data Languages with Decidable Emptiness Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Pebble Automata for Data Languages with Decidable Emptiness Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-89653