Linear grammars with one-sided contexts and their automaton representation

DOI10.1051/ITA/2015004MaRDI QIDQ5501864zbMATH OpenOpenAlexFDO

Authors Mikhail Barash, Alexander Okhotin

Publication date 14 August 2015

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/2771e3e26079d36f9d94310869cd5de4a35e32f1

zbMATH Keywords

cellular automataconjunctive grammarscontext-free grammarscontextstrellis automataundecidability

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Cellular automata (computational aspects) (68Q80)

Recommendations

• Linear grammars with one-sided contexts and their automaton representation
• An extension of context-free grammars with one-sided context specifications
• One-Nonterminal Conjunctive Grammars over a Unary Alphabet
• Comparing linear conjunctive languages to subfamilies of the context-free languages
• Nonterminal complexity of one-sided random context grammars

Cites work

• A property of real-time trellis automata
• An extension of context-free grammars with one-sided context specifications
• Characterizations and computational complexity of systolic trellis automata
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• Homomorphisms preserving linear conjunctive languages
• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Improved normal form for grammars with one-sided contexts
• On real time one-way cellular array
• On the closure properties of linear conjunctive languages.
• One-way bounded cellular automata
• Parsing algorithms with backtrack
• Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
• Systolic trellis automatata †
• Systolic trellis automatat†

Cited in

(8)

• Linear-space recognition for grammars with contexts
• Context-free grammars with lookahead
• An extension of context-free grammars with one-sided context specifications
• Generalized LR parsing algorithm for grammars with one-sided contexts
• Input-driven languages are linear conjunctive
• On translating Lambek grammars with one division into context-free grammars
• Linear grammars with one-sided contexts and their automaton representation
• The hardest language for grammars with context operators

This page was built for publication: Linear grammars with one-sided contexts and their automaton representation

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