Linear-space recognition for grammars with contexts
From MaRDI portal
Publication:1704576
DOI10.1016/j.tcs.2017.11.006zbMath1388.68152OpenAlexW2768697761MaRDI QIDQ1704576
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
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parsing by matrix multiplication generalized to Boolean grammars
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- A simple P-complete problem and its language-theoretic representations
- A game-theoretic characterization of Boolean grammars
- LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata
- Characterizations and computational complexity of systolic trellis automata
- Well-founded semantics for Boolean grammars
- Unambiguous Boolean grammars
- Simulation of one-way cellular automata by Boolean circuits
- A property of real-time trellis automata
- Definite clause grammars for language analysis - A survey of the formalism and a comparison with augmented transition networks
- On multiple context-free grammars
- General context-free recognition in less than cubic time
- Boolean grammars
- An extension of context-free grammars with one-sided context specifications
- Improved normal form for grammars with one-sided contexts
- Two-sided context specifications in formal grammars
- Generalized LR parsing algorithm for grammars with one-sided contexts
- On certain formal properties of grammars
- The recognition of deterministic CFLs in small time and space
- A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
- Recognizing Two-Sided Contexts in Cubic Time
- Linear grammars with one-sided contexts and their automaton representation
This page was built for publication: Linear-space recognition for grammars with contexts
