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 条
  • [21] Deleting Deterministic Restarting Automata with Two Windows
    Mraz, Frantisek
    Otto, Friedrich
    DEVELOPMENTS IN LANGUAGE THEORY, DLT 2017, 2017, 10396 : 272 - 283
  • [22] Free Word-Order and Restarting Automata
    Mraz, Frantisek
    Otto, Friedrich
    Platek, Martin
    FUNDAMENTA INFORMATICAE, 2014, 133 (04) : 399 - 419
  • [23] ON DETERMINISTIC CD-SYSTEMS OF RESTARTING AUTOMATA
    Messerschmidt, Hartmut
    Otto, Friedrich
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2009, 20 (01) : 185 - 209
  • [24] On restarting automata with auxiliary symbols and small window size*
    Mraz, Frantsek
    Otto, Friedrich
    RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2021, 55
  • [25] ON THE CLASSES OF LANGUAGES ACCEPTED BY LIMITED CONTEXT RESTARTING AUTOMATA
    Otto, Friedrich
    Cerno, Peter
    Mraz, Frantisek
    RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2014, 48 (01): : 61 - 84
  • [26] Restarting Automata for Picture Languages: A Survey on Recent Developments
    Otto, Friedrich
    IMPLEMENTATION AND APPLICATION OF AUTOMATA, CIAA 2014, 2014, 8587 : 16 - 41
  • [27] On Shrinking Restarting Automata of Window Size One and Two
    Mraz, Frantisek
    Otto, Friedrich
    DEVELOPMENTS IN LANGUAGE THEORY, DLT 2019, 2019, 11647 : 140 - 153
  • [28] On deterministic ordered restart-delete automata
    Otto, Friedrich
    THEORETICAL COMPUTER SCIENCE, 2019, 795 : 257 - 274
  • [29] On Ordered RRWW-Automata
    Kwee, Kent
    Otto, Friedrich
    DEVELOPMENTS IN LANGUAGE THEORY, DLT 2016, 2016, 9840 : 268 - 279
  • [30] An Online Induction Algorithm for Internal Contextual Grammars using Restarting Automata
    Midya, Abhisek
    Kuppusamy, Lakshmanan
    Sumitha, V. S.
    INTERNATIONAL CONFERENCE ON EMERGING TRENDS IN ENGINEERING, SCIENCE AND TECHNOLOGY (ICETEST - 2015), 2016, 24 : 1514 - 1521
12345