The hardest linear conjunctive language

DOI10.1016/S0020-0190(02)00511-2zbMath1162.68474MaRDI QIDQ1007613

Alexander Okhotin

Publication date: 23 March 2009

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexityformal languagesconjunctive grammarsTrellis automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (5)

On the number of nonterminals in linear conjunctive grammars ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ A simple P-complete problem and its language-theoretic representations ⋮ Complexity of equations over sets of natural numbers ⋮ Unambiguous Boolean grammars

Cites Work

• On real-time cellular automata and trellis automata
• A recognition and parsing algorithm for arbitrary conjunctive grammars.
• On the closure properties of linear conjunctive languages.
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The hardest linear conjunctive language