Linear-space recognition for grammars with contexts

DOI10.1016/J.TCS.2017.11.006MaRDI QIDQ1704576zbMATH OpenOpenAlexFDO

Authors Mikhail Barash, Alexander Okhotin

Publication date 12 March 2018

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

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

zbMATH Keywords

context-free grammarsparsingspace complexityconjunctive grammarscontext-sensitive grammars

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Recommendations

• Generalized LR parsing for grammars with contexts
• Generalized LR parsing algorithm for grammars with one-sided contexts
• Grammars with two-sided contexts
• An extension of context-free grammars with one-sided context specifications
• Two-sided context specifications in formal grammars

Cites work

• scientific article; zbMATH DE number 3978426 (Why is no real title available?)
• scientific article; zbMATH DE number 3664336 (Why is no real title available?)
• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• scientific article; zbMATH DE number 941397 (Why is no real title available?)
• scientific article; zbMATH DE number 3428547 (Why is no real title available?)
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• A game-theoretic characterization of Boolean grammars
• A property of real-time trellis automata
• A simple P-complete problem and its language-theoretic representations
• An extension of context-free grammars with one-sided context specifications
• Boolean grammars
• Characterizations and computational complexity of systolic trellis automata
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Definite clause grammars for language analysis - A survey of the formalism and a comparison with augmented transition networks
• General context-free recognition in less than cubic time
• Generalized LR parsing algorithm for grammars with one-sided contexts
• Improved normal form for grammars with one-sided contexts
• LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata
• Linear grammars with one-sided contexts and their automaton representation
• On certain formal properties of grammars
• On multiple context-free grammars
• Parsing by matrix multiplication generalized to Boolean grammars
• Recognizing two-sided contexts in cubic time
• Simulation of one-way cellular automata by Boolean circuits
• The recognition of deterministic CFLs in small time and space
• Two-sided context specifications in formal grammars
• Unambiguous Boolean grammars
• Well-founded semantics for Boolean grammars

Cited in

(6)

• Synchronous context-free grammars and optimal linear parsing strategies
• On some open problems about marcus contextual languages
• scientific article; zbMATH DE number 1952666 (Why is no real title available?)
• The hardest language for grammars with context operators
• A cubic time extensions of context-free grammars
• Using linear positional grammars for the LR parsing of 2-D symbolic languages

This page was built for publication: Linear-space recognition for grammars with contexts

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