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.017MaRDI QIDQ840776zbMATH OpenOpenAlexFDO

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

Recommendations

• A Measure for the Degree of Nondeterminism of Context-Free Languages
• Restarting automata with restricted utilization of auxiliary symbols
• scientific article; zbMATH DE number 7444013
• Ambiguity by restarting automata
• On lexicalized well-behaved restarting automata that are monotone

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 2086618 (Why is no real title available?)
• scientific article; zbMATH DE number 1394484 (Why is no real title available?)
• Growing context-sensitive languages and Church-Rosser languages
• Infinite convergent string-rewriting systems and cross-sections for finitely presented monoids
• Measuring nondeterminism in pushdown automata
• Membership for growing context-sensitive grammars is polynomial
• Nondeterminism degrees for context-free languages
• On measuring nondeterminism in regular languages
• Recent advances in formal languages and applications.

Cited in

(5)

• A Measure for the Degree of Nondeterminism of Context-Free Languages
• scientific article; zbMATH DE number 7444013 (Why is no real title available?)
• Ambiguity by restarting automata
• On h-lexicalized restarting list automata
• One-Way Restarting Automata and Their Sensitivitys

Describes a project that uses

Uses Software

• UCFL

This page was built for publication: The degree of word-expansion of lexicalized RRWW-automata - A new measure for the degree of nondeterminism of (context-free) languages

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