Hierarchies of weakly monotone restarting automata

DOI10.1051/ITA:2005021MaRDI QIDQ3025320zbMATH OpenOpenAlexFDO

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, http://www.numdam.org/item?id=ITA_2005__39_2_325_0/, https://eudml.org/doc/92769

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)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 1189300 (Why is no real title available?)
• scientific article; zbMATH DE number 1394484 (Why is no real title available?)
• scientific article; zbMATH DE number 2245557 (Why is no real title available?)
• Church-Rosser Thue systems and formal languages
• Membership for growing context-sensitive grammars is polynomial
• The uniform conjugacy problem for finite church—Rosser thue systems is NP-complete

Cited in

(12)

• Hierarchical Relaxations of the Correctness Preserving Property for Restarting Automata
• A Complete Taxonomy of Restarting Automata without Auxiliary Symbols*
• Sequential monotonicity for restarting automata
• scientific article; zbMATH DE number 1747447 (Why is no real title available?)
• scientific article; zbMATH DE number 1394484 (Why is no real title available?)
• 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

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)