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

共 33 条

[1]

[Anonymous], 1984, THESIS STANFORD U

[2]

Bresnan J. W., 1983, LINGUIST INQ, V13, P613

[3] Growing context-sensitive languages and Church-Rosser languages [J].

Buntrock, G ;

Otto, F .

INFORMATION AND COMPUTATION, 1998, 141 (01) :1-36

[4]

Buntrock G., 1996, THESIS U WURZBURG

[5] MEMBERSHIP FOR GROWING CONTEXT-SENSITIVE GRAMMARS IS POLYNOMIAL [J].

DAHLHAUS, E ;

WARMUTH, MK .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1986, 33 (03) :456-472

[6]

DIKOVSKY A, 2000, TRAITEMENT AUTOMATIQ, V41, P79

[7]

Gazdar G., 1988, Natural Language Parsing and Linguistic Theories, P69

[8]

Jancar P., 1999, Journal of Automata, Languages and Combinatorics, V4, P287

[9]

JANCAR P, 1996, DEV LANGUAGE THEORY, V2, P102

[10]

JANCAR P, 1995, LNCS, V965, P283

← 1 2 3 4 →