Hierarchies of weakly monotone restarting automata

DOI10.1051/ita:2005021zbMath1101.68587OpenAlexW2140826517MaRDI QIDQ3025320

František Mráz, Friedrich Otto

Publication date: 13 July 2005

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2005__39_2_325_0

zbMATH Keywords

hierarchiesweak monotonicityRestarting automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Grammars and rewriting systems (68Q42)

Related Items

Marcus \(t\)-contextual grammars and cut hierarchies and monotonicity for restarting automata ⋮ Degrees of non-monotonicity for restarting automata ⋮ A Complete Taxonomy of Restarting Automata without Auxiliary Symbols* ⋮ Restarting automata with auxiliary symbols restricted by lookahead size

Cites Work

• Membership for growing context-sensitive grammars is polynomial
• The uniform conjugacy problem for finite church—Rosser thue systems is NP-complete
• Church-Rosser Thue systems and formal languages
• Unnamed Item
• Unnamed Item
• Unnamed Item