Reachability Problems - 6th International Workshop, RP 2012, Bordeaux, France, September 17-19, 2012. Proceedings
Reachability Problems - 6th International Workshop, RP 2012, Bordeaux, France, September 17-19, 2012. Proceedings
复制标题
可达性问题 - 第六届国际研讨会，RP 2012，法国波尔多，2012 年 9 月 17-19 日。会议记录
DOI：
10.1007/978-3-642-33512-9_6
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Haase C
中科院分区：
文献类型：
--
作者：
Haase C
建立了时间自动机和空间有界计数器自动机的可达性问题之间的关系。我们证明了具有三个或更多时钟的时间自动机的可达性与具有两个计数器的空间有界计数器自动机的可达性是自然的对数空间可约的。进一步证明了双时钟定时自动机和空间有界单计数器自动机的可达性的对数空间等价性。最后一种简化为两个问题提供了新的见解，这两个问题的精确计算复杂性已经被独立地确定为开放的。
This paper establishes a relationship between reachability problems in timed automata and space-bounded counter automata. We show that reachability in timed automata with three or more clocks is naturally logarithmic-space interreducible with reachability in space-bounded counter automata with two counters. We moreover show the logarithmic-space equivalence of reachability in two-clock timed automata and space-bounded one-counter automata. This last reduction provides new insight into two problems whose precise computational complexity have independently been identified as open.