On the complexity of 2-monotone restarting automata

被引：5

作者：

Jurdzinski, Tomasz ^{[2
]}

Otto, Friedrich ^{[1
]}

Mraz, Frantiek ^{[3
]}

Platek, Martin ^{[3
]}

机构：

[1] Univ Kassel, Fachbereich Elektrotechn Informat, D-34109 Kassel, Germany

[2] Univ Wroclaw, Inst Comp Sci, PL-51151 Wroclaw, Poland

[3] Charles Univ Prague, Fac Math & Phys, Dept Comp Sci, Prague 11800 1, Czech Republic

来源：

THEORY OF COMPUTING SYSTEMS | 2008年 / 42卷 / 04期

关键词：

restarting automaton; monotonicity; NP-completeness; growing context-sensitive language;

D O I：

10.1007/s00224-007-9004-y

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The R-automaton is the weakest form of the nondeterministic version of the restarting automaton that was introduced by Jancar et al. to model the so-called analysis by reduction. Here it is shown that the class L(R) of languages that are accepted by R-automata is incomparable under set inclusion to the class CRL of Church-Rosser languages and to the class GCSL of growing context-sensitive languages. In fact this already holds for the class L(2-mon-R) of languages that are accepted by 2-monotone R-automata. In addition, we prove that already the latter class contains NP-complete languages, showing that already the 2-monotone R-automaton has a surprisingly large expressive power.

引用

页码：488 / 518

页数：31