Two-sided context specifications in formal grammars

DOI10.1016/J.TCS.2015.05.004zbMATH Open1408.68086OpenAlexW617375748MaRDI QIDQ2354409FDOQ2354409

Authors: Mikhail Barash, Alexander Okhotin 

Publication date: 13 July 2015

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

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

Recommendations

• Grammars with two-sided contexts
• An extension of context-free grammars with one-sided context specifications
• Improved normal form for grammars with one-sided contexts
• Defining contexts in context-free grammars
• Generalized LR parsing algorithm for grammars with one-sided contexts

zbMATH Keywords

context-free grammarsparsingconjunctive grammarscontext-sensitive grammarsgrammars with contexts

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On certain formal properties of grammars
• General context-free recognition in less than cubic time
• Boolean grammars
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Title not available (Why is that?)
• Two Families of Languages Related to ALGOL
• On multiple context-free grammars
• BOOLEAN FUZZY SETS
• Parsing by matrix multiplication generalized to Boolean grammars
• Well-founded semantics for Boolean grammars
• Conjunctive grammars and systems of language equations
• \(LR(0)\) conjunctive grammars and deterministic synchronized alternating pushdown automata
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• An extension of context-free grammars with one-sided context specifications
• Recognizing two-sided contexts in cubic time
• Improved normal form for grammars with one-sided contexts
• Generalized LR parsing for grammars with contexts

Cited In (10)

• Grammars with two-sided contexts
• Title not available (Why is that?)
• The hardest language for grammars with context operators
• An extension of context-free grammars with one-sided context specifications
• Hardest languages for conjunctive and Boolean grammars
• Defining contexts in context-free grammars
• Improved normal form for grammars with one-sided contexts
• Linear-space recognition for grammars with contexts
• The hardest language for conjunctive grammars
• Generalized LR parsing algorithm for grammars with one-sided contexts

Uses Software

• ALGOL 60

This page was built for publication: Two-sided context specifications in formal grammars

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