Two-dimensional hierarchies of proper languages of lexicalized FRR-automata

DOI10.1016/j.ic.2009.02.011zbMath1192.68420OpenAlexW1972330283MaRDI QIDQ1041046

František Mráz, Friedrich Otto, Martin Plátek

Publication date: 27 November 2009

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2009.02.011

zbMATH Keywords

lexicalizationrestarting automatonanalysis by reductionlanguage classesword-order complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Degrees of non-monotonicity for restarting automata
• On measuring nondeterminism in regular languages
• On the complexity of 2-monotone restarting automata
• Growing context-sensitive languages and Church-Rosser languages
• Recent advances in formal languages and applications.
• Measuring nondeterminism in pushdown automata
• SHRINKING RESTARTING AUTOMATA
• A Measure for the Degree of Nondeterminism of Context-Free Languages