Conjunctive grammars and systems of language equations

DOI10.1023/A:1020213411126zbMath1036.68063OpenAlexW1512779672MaRDI QIDQ1403252

Alexander Okhotin

Publication date: 1 September 2003

Published in: Programming and Computer Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1020213411126

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (19)

On the closure properties of linear conjunctive languages. ⋮ Boolean grammars ⋮ On the equivalence of linear conjunctive grammars and trellis automata ⋮ On the number of nonterminals in linear conjunctive grammars ⋮ Language equations with complementation: decision problems ⋮ LINEAR CONJUNCTIVE GRAMMARS AND ONE-TURN SYNCHRONIZED ALTERNATING PUSHDOWN AUTOMATA ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ One-nonterminal conjunctive grammars over a unary alphabet ⋮ CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES ⋮ A CHARACTERIZATION OF THE ARITHMETICAL HIERARCHY BY LANGUAGE EQUATIONS ⋮ An extension of context-free grammars with one-sided context specifications ⋮ The Hardest Language for Conjunctive Grammars ⋮ Decision problems for language equations ⋮ Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth ⋮ Least and greatest solutions of equations over sets of integers ⋮ Language equations ⋮ The dual of concatenation ⋮ Two-sided context specifications in formal grammars ⋮ Unresolved systems of language equations: expressive power and decision problems

This page was built for publication: Conjunctive grammars and systems of language equations