On pebble automata for data languages with decidable emptiness problem
Journal
Journal of Computer and System Sciences
Journal Volume
76
Journal Issue
8
Pages
778-791
Date Issued
2010
Author(s)
TONY TAN
Abstract
In this paper we study a subclass of pebble automata (PA) for data languages for which the emptiness problem is decidable. Namely, we show that the emptiness problem for weak 2-pebble automata is decidable, while the same problem for weak 3-pebble automata is undecidable. We also 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 still decidable. It is also robust: alternating, non-deterministic and deterministic top view weak PA have the same recognition power; and are strong enough to accept all data languages expressible in Linear Temporal Logic with the future-time operators, augmented with one register freeze quantifier. © 2010 Elsevier Inc. All rights reserved.
Subjects
Decidability; Finite state automata; Infinite alphabet
Other Subjects
Automata theory; Computability and decidability; Finite automata; Data values; Emptiness problem; Equality tests; Freeze quantifiers; Infinite alphabet; Linear temporal logic; Top views; Robots
Type
journal article