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 条

[21] Descriptional complexity of unambiguous input-driven pushdown automata
Okhotin, Alexander
Salomaa, Kai
[J]. THEORETICAL COMPUTER SCIENCE, 2015, 566 : 1 - 11
[22] From Finite Automata to Regular Expressions and Back - A Summary on Descriptional Complexity
Gruber, Hermann
Holzer, Markus
[J]. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2015, 26 (08) : 1009 - 1040
[23] Descriptional complexity of two-way pushdown automata with restricted head reversals
Malcher, Andreas
Mereghetti, Carlo
Palano, Beatrice
[J]. THEORETICAL COMPUTER SCIENCE, 2012, 449 : 119 - 133
[24] Weighted restarting automata
Friedrich Otto
Qichao Wang
[J]. Soft Computing, 2018, 22 : 1067 - 1083
[25] Weighted restarting automata
Otto, Friedrich
Wang, Qichao
[J]. SOFT COMPUTING, 2018, 22 (04) : 1067 - 1083
[26] Descriptional Complexity of Non-Unary Self-Verifying Symmetric Difference Automata
Marais, Laurette
van Zijl, Lynette
[J]. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2022, 33 (03N04) : 313 - 333
[27] NONDETERMINISTIC BIAUTOMATA AND THEIR DESCRIPTIONAL COMPLEXITY
Holzer, Markus
Jakobi, Sebastian
[J]. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2014, 25 (07) : 837 - 855
[28] On the descriptional complexity of iterative arrays
Malcher, A
[J]. IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2004, E87D (03) : 721 - 725
[29] Sequential monotonicity for restarting automata
Jurdzinski, Tomasz
Otto, Friedrich
[J]. RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2007, 41 (02): : 157 - 175
[30] Descriptional complexity of splicing systems
Loos, Remco
Malcher, Andreas
Wotschke, Detlef
[J]. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2008, 19 (04) : 813 - 826

← 1 2 3 4 5 →