Reversible Ordered Restarting Automata

被引：3
|
作者：
Otto, Friedrich [1 ]
Wendlandt, Matthias [2 ]
Kwee, Kent [1 ]
机构：
[1] Univ Kassel, Fachbereich Elektrotech Informat, D-34109 Kassel, Germany
[2] Univ Giessen, Inst Informat, D-35392 Giessen, Germany
来源：
REVERSIBLE COMPUTATION, RC 2015 | 2015年 / 9138卷
关键词：
Restarting automaton; Reversibility; Descriptional complexity;
D O I：
10.1007/978-3-319-20860-2_4
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Stateless deterministic ordered restarting automata characterize the class of regular languages. Here we introduce a notion of reversibility for these automata and show that each regular language is accepted by such a reversible stateless deterministic ordered restarting automaton. We study the descriptional complexity of these automata, showing that they are exponentially more succinct than nondeterministic finite-state acceptors. We also look at the case of unary input alphabets.
引用
收藏
页码：60 / 75
页数：16
相关论文
共 50 条
12345