On the closure properties of linear conjunctive languages.

DOI10.1016/S0304-3975(02)00543-1zbMath1042.68069OpenAlexW2073577522MaRDI QIDQ1874415

Alexander Okhotin

Publication date: 25 May 2003

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00543-1

zbMATH Keywords

linear conjunctive grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Boolean grammars ⋮ On the equivalence of linear conjunctive grammars and trellis automata ⋮ On the number of nonterminals in linear conjunctive grammars ⋮ LINEAR CONJUNCTIVE GRAMMARS AND ONE-TURN SYNCHRONIZED ALTERNATING PUSHDOWN AUTOMATA ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ Expressive power of \(\text{LL}(k)\) Boolean grammars ⋮ The hardest linear conjunctive language ⋮ Domain mu-calculus ⋮ Linear grammars with one-sided contexts and their automaton representation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On equations for regular languages, finite automata, and sequential networks
• Some subclasses of context-free languages in \(NC^ 1\)
• A recognition and parsing algorithm for arbitrary conjunctive grammars.
• Conjunctive grammars and systems of language equations
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• On a family of linear grammars
• The Unsolvability of the Recognition of Linear Context-Free Languages
• A machine realization of the linear context-free languages
• The undecidability of the ambiguity problem for minimal linear grammars