On pebble automata for data languages with decidable emptiness problem

Tony Tan

Research output: Contribution to journalArticlepeer-review

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. (C) 2010 Elsevier Inc. All rights reserved.

Original languageEnglish
Pages (from-to)778-791
Number of pages14
JournalJournal of Computer and System Sciences
Volume76
Issue number8
DOIs
Publication statusPublished - Dec 2010

Cite this