Reachability in two-clock timed automata is PSPACE-complete
Reachability in two-clock timed automata is PSPACE-complete
复制标题
DOI：
10.1016/j.ic.2014.12.004
复制
发表时间：
2013-02
期刊：
影响因子：
--
通讯作者：
John Fearnley;M. Jurdzinski
中科院分区：
文献类型：
--
作者：
John Fearnley;M. Jurdzinski
最近，Haase，Ouakine和Worrell证明了两时钟时间自动机的可达性等价于有界单计数器自动机的可达性。我们证明了有界单计数器自动机的可达性是PSPACE-完全的。
Recently, Haase, Ouaknine, and Worrell have shown that reachability in two-clock timed automata is log-space equivalent to reachability in bounded one-counter automata. We show that reachability in bounded one-counter automata is PSPACE-complete.