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 条
  • [31] On the Expressive Power of Stateless Ordered Restart-Delete Automata
    Otto, Friedrich
    THEORY OF COMPUTING SYSTEMS, 2021, 65 (07) : 1033 - 1068
  • [32] On the Expressive Power of Stateless Ordered Restart-Delete Automata
    Friedrich Otto
    Theory of Computing Systems, 2021, 65 : 1033 - 1068
  • [33] CD-Systems of Restarting Automata Governed by Explicit Enable and Disable Conditions
    Otto, Friedrich
    SOFSEM 2010: THEORY AND PRACTICE OF COMPUTER SCIENCE, PROCEEDINGS, 2010, 5901 : 627 - 638
  • [34] Marcus t-contextual grammars and cut hierarchies and monotonicity for restarting automata
    Mraz, F.
    Otto, F.
    Platek, M.
    Jurdzinski, T.
    THEORETICAL COMPUTER SCIENCE, 2006, 366 (03) : 272 - 296
  • [35] Universality of reversible hexagonal cellular automata
    Morita, K
    Margenstern, N
    Imai, K
    RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 1999, 33 (06): : 535 - 550
  • [36] Minimal Reversible Deterministic Finite Automata
    Holzer, Markus
    Jakobi, Sebastian
    Kutrib, Martin
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2018, 29 (02) : 251 - 270
  • [37] On Deterministic Ordered Restart-Delete Automata
    Otto, Friedrich
    DEVELOPMENTS IN LANGUAGE THEORY, DLT 2018, 2018, 11088 : 529 - 540
  • [38] A Study on Reversible Rules of Probabilistic Cellular Automata
    Pattanayak, Anupam
    Dhal, Subhasish
    2020 IEEE CALCUTTA CONFERENCE (CALCON), 2020, : 39 - 44
  • [39] Evolutionary algorithms for designing reversible cellular automata
    Mariot, Luca
    Picek, Stjepan
    Jakobovic, Domagoj
    Leporati, Alberto
    GENETIC PROGRAMMING AND EVOLVABLE MACHINES, 2021, 22 (04) : 429 - 461
  • [40] Cellular automata reversible over limit set
    Taati, Siamak
    JOURNAL OF CELLULAR AUTOMATA, 2007, 2 (02) : 167 - 177
12345