Reachability in Two-Clock Timed Automata Is PSPACE-Complete

机译：双时钟定时自动机的可达性是pspace-complete

获取原文

页面导航

摘要
著录项
相似文献
相关主题

摘要

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.

机译：HAASE，OUKNINE和Worrell表明，两个时钟定时自动机中的可达性是相当于界限单反自动机的可达性的对数空间。我们展示了界限的单反自动机中的可达性是PSPACE完整的。

著录项

来源
《International colloquium on automata, languages and programming》|2013年||共12页
会议地点
作者
John Fearnley; Marcin Jurdzinski;
展开▼
作者单位

展开▼
会议组织
原文格式 PDF
正文语种
中图分类程序设计、软件工程;
关键词

相似文献

外文文献
中文文献
专利

1. Reachability in two-clock timed automata is PSPACE-complete [J] . John Fearnley, Martin Jurdzinski Information and computation . 2015,第auga期

机译：两时钟定时自动机的可达性是PSPACE-complete
2. PSPACE-complete problems for subgroups of free groups and inverse finite automata [J] . Birget JC., Meakin J., Weil P., Theoretical computer science . 2000,第1a2期

机译：自由群和逆有限自动机的子群的PSPACE-完全问题
3. Reachability relations of timed pushdown automata [J] . Lorenzo Clemente, Slawomir Lasota Journal of computer and system sciences . 2021,第May期

机译：定时推动自动机的可达性关系
4. Reachability in Two-Clock Timed Automata Is PSPACE-Complete [C] . John Fearnley, Marcin Jurdzinski International colloquium on automata, languages and programming . 2013

机译：两时钟定时自动机的可达性是PSPACE完整的
5. Modeling timing faults using timed extended finite state machines and extended timed automata. [D] . Wang, Yu. 2009

机译：使用定时扩展有限状态机和扩展定时自动机对定时故障进行建模。
6. Heart Rhythm Insights Into Structural Remodeling in Atrial Tissue: Timed Automata Approach [O] . Danuta Makowiec, Joanna Wdowczyk, Zbigniew R. Struzik -1

机译：心律对心房组织结构重塑的认识：定时自动机方法
7. Reachability in two-clock timed automata is PSPACE-complete [O] . Fearnley J, Jurdziński M 2015

机译：两时钟定时自动机的可达性是PSPACE-complete

Reachability in Two-Clock Timed Automata Is PSPACE-Complete

摘要

著录项

相似文献

相关主题

期刊订阅