Linear-space recognition for grammars with contexts
From MaRDI portal
Publication:1704576
DOI10.1016/J.TCS.2017.11.006zbMATH Open1388.68152OpenAlexW2768697761MaRDI QIDQ1704576FDOQ1704576
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
Recommendations
Cites Work
- Title not available (Why is that?)
- On certain formal properties of grammars
- General context-free recognition in less than cubic time
- Boolean grammars
- Title not available (Why is that?)
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- Title not available (Why is that?)
- On multiple context-free grammars
- Title not available (Why is that?)
- Parsing by matrix multiplication generalized to Boolean grammars
- A game-theoretic characterization of Boolean grammars
- Well-founded semantics for Boolean grammars
- Unambiguous Boolean grammars
- A property of real-time trellis automata
- A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
- Title not available (Why is that?)
- A simple P-complete problem and its language-theoretic representations
- Characterizations and computational complexity of systolic trellis automata
- The recognition of deterministic CFLs in small time and space
- An extension of context-free grammars with one-sided context specifications
- Linear grammars with one-sided contexts and their automaton representation
- LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata
- Definite clause grammars for language analysis - A survey of the formalism and a comparison with augmented transition networks
- Generalized LR parsing algorithm for grammars with one-sided contexts
- Simulation of one-way cellular automata by Boolean circuits
- Improved normal form for grammars with one-sided contexts
- Two-sided context specifications in formal grammars
- Recognizing two-sided contexts in cubic time
Cited In (6)
- A cubic time extensions of context-free grammars
- The hardest language for grammars with context operators
- Synchronous context-free grammars and optimal linear parsing strategies
- Title not available (Why is that?)
- On some open problems about marcus contextual languages
- 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)
