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 条
[41]   Descriptional Complexity of Pushdown Store Languages [J].
Malcher, Andreas ;
Meckel, Katja ;
Mereghetti, Carlo ;
Palano, Beatrice .
DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2012, 2012, 7386 :209-221
[42]   Descriptional complexity of generalized forbidding grammars [J].
Meduna, A ;
Svec, M .
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2003, 80 (01) :11-17
[43]   Parikh's Theorem and Descriptional Complexity [J].
Lavado, Giovanna J. ;
Pighizzini, Giovanni .
SOFSEM 2012: THEORY AND PRACTICE OF COMPUTER SCIENCE, 2012, 7147 :361-372
[44]   On the descriptional complexity of metalinear CD grammar systems [J].
Sunckel, B .
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2005, 16 (05) :1011-1025
[45]   Restarting automata with restricted utilization of auxiliary symbols [J].
Jurdzinski, Tomasz ;
Otto, Friedrich .
THEORETICAL COMPUTER SCIENCE, 2006, 363 (02) :162-181
[46]   Descriptional complexity of semi-conditional grammars [J].
Masopust, Tomas ;
Meduna, Alexander .
INFORMATION PROCESSING LETTERS, 2007, 104 (01) :29-31
[47]   Descriptional complexity of multi-parallel grammars [J].
Masopust, Tomas .
INFORMATION PROCESSING LETTERS, 2008, 108 (02) :68-70
[48]   One-Way Restarting Automata and Their Sensitivity [J].
Platek, Martin ;
Otto, Friedrich ;
Mraz, Frantisek .
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2022, 33 (03N04) :371-387
[49]   On Ordered RRWW-Automata [J].
Kwee, Kent ;
Otto, Friedrich .
DEVELOPMENTS IN LANGUAGE THEORY, DLT 2016, 2016, 9840 :268-279
[50]   Free Word-Order and Restarting Automata [J].
Mraz, Frantisek ;
Otto, Friedrich ;
Platek, Martin .
FUNDAMENTA INFORMATICAE, 2014, 133 (04) :399-419
12345