https://scholars.lib.ntu.edu.tw/handle/123456789/490130
Title: | On pebble automata for data languages with decidable emptiness problem | Authors: | TONY TAN | Keywords: | Decidability; Finite state automata; Infinite alphabet | Issue Date: | 2010 | Journal Volume: | 76 | Journal Issue: | 8 | Start page/Pages: | 778-791 | Source: | Journal of Computer and System Sciences | 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. |
URI: | https://scholars.lib.ntu.edu.tw/handle/123456789/490130 https://www.scopus.com/inward/record.uri?eid=2-s2.0-84865720175&doi=10.1016%2fj.jcss.2010.03.004&partnerID=40&md5=9e384bf5f62cacc8471eb7ad8e96b47a |
ISSN: | 00220000 | DOI: | 10.1016/j.jcss.2010.03.004 | SDG/Keyword: | Automata theory; Computability and decidability; Finite automata; Data values; Emptiness problem; Equality tests; Freeze quantifiers; Infinite alphabet; Linear temporal logic; Top views; Robots |
Appears in Collections: | 資訊工程學系 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.