On the Descriptional Complexity of Deterministic Ordered Restarting Automata

被引：0
作者：
Otto, Friedrich [1 ]
机构：
[1] Univ Kassel, Fachbereich Elektrotech Informat, D-34109 Kassel, Germany
来源：
DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2014 | 2014年 / 8614卷
关键词：
restarting automaton; ordered rewriting; descriptional complexity; language operations;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We show that the deterministic ordered restarting automaton is polynomially related in size to the weight-reducing Hennie machine. Accordingly, it allows very compact representations of (some) regular languages. In addition, we investigate the descriptional complexity of the operations of reversal, complementation, intersection, and union for regular languages that are given through stateless deterministic ordered restarting automata.
引用
收藏
页码：318 / 329
页数：12
相关论文
共 50 条
[31]   Restarting Automata for Insertion Languages [J].
Kuppusamy, Lakshmanan ;
Midya, Abhisek .
2013 4TH NIRMA UNIVERSITY INTERNATIONAL CONFERENCE ON ENGINEERING (NUICONE 2013), 2013,
[32]   A hierarchy of jumping restarting automata [J].
Wang, Qichao ;
Li, Yongming .
INFORMATION SCIENCES, 2024, 657
[33]   Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds [J].
Pighizzini, G ;
Shallit, J ;
Wang, MW .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2002, 65 (02) :393-414
[34]   ON STATELESS TWO-PUSHDOWN AUTOMATA AND RESTARTING AUTOMATA [J].
Kutrib, Martin ;
Messerschmidt, Hartmut ;
Otto, Friedrich .
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2010, 21 (05) :781-798
[35]   On Descriptional Complexity of Partially Parallel Grammars [J].
Masopust, Tomas ;
Meduna, Alexander .
FUNDAMENTA INFORMATICAE, 2008, 87 (3-4) :407-415
[36]   Descriptional complexity of NFA of different ambiguity [J].
Leung, H .
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2005, 16 (05) :975-984
[37]   Descriptional complexity of machines with limited resources [J].
Goldstine, J .
JOURNAL OF UNIVERSAL COMPUTER SCIENCE, 2002, 8 (02) :193-234
[38]   On the descriptional complexity of scattered context grammars [J].
Masopust, Tomas .
THEORETICAL COMPUTER SCIENCE, 2009, 410 (01) :108-112
[39]   Cooperating distributed systems of restarting automata [J].
Messerschmidt, Hartmut ;
Otto, Friedrich .
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2007, 18 (06) :1333-1342
[40]   SYSTEMS OF PARALLEL COMMUNICATING RESTARTING AUTOMATA [J].
Vollweiler, Marcel ;
Otto, Friedrich .
RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2014, 48 (01) :3-22
12345