Reachability in pushdown register automata
Reachability in pushdown register automata
复制标题
下推寄存器自动机的可达性
DOI：
10.1016/j.jcss.2017.02.008
复制
发表时间：
2017
影响因子：
1.1
通讯作者：
Murawski A
中科院分区：
文献类型：
--
作者：
Murawski A
我们研究了无限字母表上的下推自动机的可达性。我们表明，在可达性/空性方面，这些机器可以忠实地表示只使用3relements的字母表，whereris寄存器的数量。我们解决了相关的可达性/空性问题的复杂性。与寄存器自动机相比，下推寄存器自动机的空问题是EXPTIME完全的，与所使用的寄存器存储策略无关。我们还解决了全球的可达性问题，表示下推配置一个特殊的寄存器自动机。最后，我们研究了下推存储的高阶扩展，并表明可达性在2阶是不可判定的。
We investigate reachability in pushdown automata over infinite alphabets. We show that, in terms of reachability/emptiness, these machines can be faithfully represented using only 3relements of the alphabet, whereris the number of registers. We settle the complexity of associated reachability/emptiness problems. In contrast to register automata, the emptiness problem for pushdown register automata is EXPTIME-complete, independent of the register storage policy used. We also solve the global reachability problem by representing pushdown configurations with a special register automaton. Finally, we examine extensions of pushdown storage to higher orders and show that reachability is undecidable at order 2.
登录
查看更多内容
IMJ 的上下文等价检查器 *
DOI：
--
发表时间：
2015
期刊：
Automated Technology for Verification and Analysis
影响因子：
--
作者：
A. Murawski;S. Ramsay;N. Tzevelekos
通讯作者：
N. Tzevelekos
算法名义游戏语义
DOI：
10.1007/978-3-642-19718-5_22
发表时间：
2011
期刊：
Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science, 2004.
影响因子：
--
作者：
A. Murawski;N. Tzevelekos
通讯作者：
N. Tzevelekos
DOI：
10.1016/s0304-3975(02)00397-3
发表时间：
2003
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
A. Bouajjani;P. Habermehl;Richard Mayr
通讯作者：
Richard Mayr
DOI：
10.1007/11874683_3
发表时间：
2006-09
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
L. Segoufin
通讯作者：
L. Segoufin
影响因子：
1.1
作者：
Sakamoto, H;Ikeda, D
通讯作者：
Ikeda, D