Two-sided context specifications in formal grammars

DOI10.1016/J.TCS.2015.05.004MaRDI QIDQ2354409zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

context-free grammarsparsingconjunctive grammarscontext-sensitive grammarsgrammars with contexts

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

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

Cites work

• scientific article; zbMATH DE number 3664336 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• An extension of context-free grammars with one-sided context specifications
• BOOLEAN FUZZY SETS
• Boolean grammars
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Conjunctive grammars and systems of language equations
• General context-free recognition in less than cubic time
• Generalized LR parsing for grammars with contexts
• Improved normal form for grammars with one-sided contexts
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• 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
• Two Families of Languages Related to ALGOL
• Well-founded semantics for Boolean grammars
• \(LR(0)\) conjunctive grammars and deterministic synchronized alternating pushdown automata

Cited in

(10)

• Generalized LR parsing algorithm for grammars with one-sided contexts
• Grammars with two-sided contexts
• scientific article; zbMATH DE number 4176487 (Why is no real title available?)
• The hardest language for grammars with context operators
• Hardest languages for conjunctive and Boolean grammars
• An extension of context-free grammars with one-sided context specifications
• 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

Describes a project that uses

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)