scientific article; zbMATH DE number 522856

MaRDI QIDQ4284250zbMATH OpenFDO

Authors Markus Holzer, Klaus-Jörn Lange

Publication date 31 August 1994

zbMATH Keywords

deterministic linear languagesformal languagesLL(1) grammarsLR(1) grammarsmembership problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• Bidirectional parsing for linear languages
• Properties of deterministic top down grammars
• scientific article; zbMATH DE number 2089362
• On the complexity of LL(k) testing
• On linear languages recognized by deterministic biautomata

Cited in

(23)

• McNaughton families of languages.
• A note on the equivalence and complexity of linear grammars
• Hardest languages for conjunctive and Boolean grammars
• Linear graph grammars: Power and complexity
• On the closure properties of linear conjunctive languages.
• A direct complement construction for LR(1) grammars
• Using linear positional grammars for the LR parsing of 2-D symbolic languages
• Syntax checking either way
• On linear languages recognized by deterministic biautomata
• Bidirectional parsing for linear languages
• On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
• A Taxonomy of Deterministic Forgetting Automata
• Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata
• Streaming algorithms for language recognition problems
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• On The Space Complexity Of Turn Bounded Pushdown Automata
• On the Transformation of LL(k)-linear Grammars to LL(1)-linear
• Leaf languages and string compression
• A COMPLEX MEASURE FOR LINEAR GRAMMARS
• On the transformation of LL(k)-linear to LL(1)-linear grammars
• Syntax checking either way
• Degrees of non-monotonicity for restarting automata
• Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}

This page was built for publication:

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