The degree of word-expansion of lexicalized RRWW-automata - A new measure for the degree of nondeterminism of (context-free) languages

DOI10.1016/j.tcs.2009.03.017zbMath1191.68399OpenAlexW2135178625MaRDI QIDQ840776

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

Publication date: 14 September 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.03.017

zbMATH Keywords

restarting automatonanalysis by reductionmeasure of nondeterminism

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Unnamed Item ⋮ One-Way Restarting Automata and Their Sensitivitys ⋮ Unnamed Item

Uses Software

• UCFL

Cites Work

• Membership for growing context-sensitive grammars is polynomial
• On measuring nondeterminism in regular languages
• Infinite convergent string-rewriting systems and cross-sections for finitely presented monoids
• Growing context-sensitive languages and Church-Rosser languages
• Recent advances in formal languages and applications.
• Measuring nondeterminism in pushdown automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item