On pebble automata for data languages with decidable emptiness problem
On pebble automata for data languages with decidable emptiness problem
复制标题
DOI：
10.1007/978-3-642-03816-7_60
复制
发表时间：
2009-08
期刊：
影响因子：
--
通讯作者：
Tony Tan
中科院分区：
文献类型：
--
作者：
Tony Tan
在本文中，我们研究了卵石自动机（PA）的一个子类的数据语言的空性问题是可判定的。也就是说，我们证明了弱2-卵石自动机的空性问题是可判定的，而弱3-卵石自动机的空性问题是不可判定的。我们还介绍了所谓的顶视弱PA。粗略地说，俯视图弱PA是仅在最近放置的两个卵石看到的数据值之间执行相等性测试的弱PA。这个模型的空性问题仍然是可判定的。
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-calledtop viewweak 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.