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 条
  • [1] Nondeterministic Ordered Restarting Automata
    Kwee, Kent
    Otto, Friedrich
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2018, 29 (04) : 663 - 685
  • [2] On the Descriptional Complexity of Deterministic Ordered Restarting Automata
    Otto, Friedrich
    DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2014, 2014, 8614 : 318 - 329
  • [3] A Pumping Lemma for Ordered Restarting Automata
    Kwee, Kent
    Otto, Friedrich
    DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2017, 2017, 10316 : 226 - 237
  • [4] Ordered Restarting Automata for Picture Languages
    Mraz, Frantisek
    Otto, Friedrich
    SOFSEM 2014: THEORY AND PRACTICE OF COMPUTER SCIENCE, 2014, 8327 : 431 - 442
  • [5] On the descriptional complexity of stateless deterministic ordered restarting automata
    Otto, Friedrich
    Kwee, Kent
    INFORMATION AND COMPUTATION, 2018, 259 : 277 - 302
  • [6] Deterministic Ordered Restarting Automata that Compute Functions
    Otto, Friedrich
    Kwee, Kent
    DEVELOPMENTS IN LANGUAGE THEORY (DLT 2015), 2015, 9168 : 401 - 412
  • [7] Extended Two-Way Ordered Restarting Automata for Picture Languages
    Otto, Friedrich
    Mraz, Frantisek
    LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS (LATA 2014), 2014, 8370 : 541 - 552
  • [8] Weighted restarting automata
    Friedrich Otto
    Qichao Wang
    Soft Computing, 2018, 22 : 1067 - 1083
  • [9] Weighted restarting automata
    Otto, Friedrich
    Wang, Qichao
    SOFT COMPUTING, 2018, 22 (04) : 1067 - 1083
  • [10] Sequential monotonicity for restarting automata
    Jurdzinski, Tomasz
    Otto, Friedrich
    RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2007, 41 (02): : 157 - 175
12345