scientific article; zbMATH DE number 522856

MaRDI QIDQ4284250zbMATH OpenFDO

Authors Markus Holzer, Klaus-Jörn Lange

Publication date 31 August 1994

zbMATH Keywords

formal languagesmembership problemLR(1) grammarsLL(1) grammarsdeterministic linear languages

Mathematics Subject Classification ID

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

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)

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

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)