Hierarchies of weakly monotone restarting automata

DOI10.1051/ITA:2005021zbMATH Open1101.68587OpenAlexW2140826517MaRDI QIDQ3025320FDOQ3025320

Authors: 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

Recommendations

• Degrees of non-monotonicity for restarting automata
• Sequential monotonicity for restarting automata
• Monotonicity of restarting automata
• Developments in Language Theory
• Restarting automata

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)

Cites Work

• Title not available (Why is that?)
• Membership for growing context-sensitive grammars is polynomial
• Church-Rosser Thue systems and formal languages
• The uniform conjugacy problem for finite church—Rosser thue systems is NP-complete
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (12)

• A Complete Taxonomy of Restarting Automata without Auxiliary Symbols*
• Sequential monotonicity for restarting automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Restarting automata with auxiliary symbols restricted by lookahead size
• Marcus \(t\)-contextual grammars and cut hierarchies and monotonicity for restarting automata
• Languages accepted by weighted restarting automata
• Degrees of non-monotonicity for restarting automata
• Weak cyclic forms of rw-automata
• A hierarchy of monotone deterministic non-forgetting restarting automata
• Hierarchies of weak automata and weak monadic formulas
• Hierarchical Relaxations of the Correctness Preserving Property for Restarting Automata

This page was built for publication: Hierarchies of weakly monotone restarting automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3025320)