On the complexity of 2-monotone restarting automata
From MaRDI portal
Publication:927391
DOI10.1007/s00224-007-9004-yzbMath1140.68034OpenAlexW2048478966MaRDI QIDQ927391
Tomasz Jurdziński, František Mráz, Friedrich Otto, Martin Plátek
Publication date: 6 June 2008
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-007-9004-y
Related Items (4)
On determinism versus nondeterminism for restarting automata ⋮ A Complete Taxonomy of Restarting Automata without Auxiliary Symbols* ⋮ Two-dimensional hierarchies of proper languages of lexicalized FRR-automata ⋮ Lambda-confluence for context rewriting systems
Cites Work
- Membership for growing context-sensitive grammars is polynomial
- Degrees of non-monotonicity for restarting automata
- Tree adjunct grammars
- Growing context-sensitive languages and Church-Rosser languages
- The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
- SHRINKING RESTARTING AUTOMATA
- Church-Rosser Thue systems and formal languages
- A scale of context sensitive languages: Applications to natural language
- The equivalence of four extensions of context-free grammars
- Developments in Language Theory
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the complexity of 2-monotone restarting automata
