Sequential monotonicity for restarting automata

被引：0

作者：

Jurdzinski, Tomasz ^{[1
]}

Otto, Friedrich

机构：

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

[2] Univ Kassel, Fachbereich Elektrotech Informat, D-34109 Kassel, Germany

来源：

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS | 2007年 / 41卷 / 02期

关键词：

restarting automaton; sequential monotonicity; hierarchies; COMPLEXITY;

D O I：

10.1051/ita:2007013

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

As already 2- monotone R- automata accept NP- complete languages, we introduce a restricted variant of j- monotonicity for restarting automata, called sequential j- monotonicity. For restarting automata without auxiliary symbols, this restricted variant still yields infinite hierarchies. However, for restarting automata with auxiliary symbols, all degrees of sequential monotonicity collapse to the first level, implying that RLWW- automata that are sequentially monotone of degree j for any j >= 1 only accept context- free languages.

引用

页码：157 / 175

页数：19

共 16 条

[1] Berstel J., 1979, Transductions and context-free languages
[2] BOOK R., 1993, String-Rewriting Systems
[3] CREMANNS R, 1993, MATH SCHRIFTEN KASSE
[4] A NOTE ON PUSHDOWN STORE AUTOMATA AND REGULAR SYSTEMS
GREIBACH, SA
[J]. PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1967, 18 (02) : 263 - &
[5] Jancar P., 1999, Journal of Automata, Languages and Combinatorics, V4, P287
[6] JANCAR P, 1995, LNCS, V965, P283
[7] Degrees of non-monotonicity for restarting automata
Jurdzinski, T.
Mraz, F.
Otto, F.
Platek, M.
[J]. THEORETICAL COMPUTER SCIENCE, 2006, 369 (1-3) : 1 - 34
[8] Jurdzinski T., 2004, Journal of Automata, Languages and Combinatorics, V9, P407
[9] Jurdzinski T, 2004, LECT NOTES COMPUT SC, V3340, P237
[10] NIEMANN G, 2003, WORDS LANGUAGES COMB, V3, P352

← 1 2 →