On the number of nonterminals in linear conjunctive grammars

DOI10.1016/j.tcs.2004.03.002zbMath1068.68072MaRDI QIDQ596108

Alexander Okhotin

Publication date: 10 August 2004

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

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

zbMATH Keywords

automaton; Cellular; Conjunctive grammar; Descriptional complexity; Formal languages; Language equation; Minimal linear grammar; Trellis automaton

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q42: Grammars and rewriting systems

Related Items

A CHARACTERIZATION OF THE ARITHMETICAL HIERARCHY BY LANGUAGE EQUATIONS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On real time one-way cellular array
• On real-time cellular automata and trellis automata
• Characterizations and computational complexity of systolic trellis automata
• The hardest linear conjunctive language
• Nonterminal complexity of programmed grammars.
• A recognition and parsing algorithm for arbitrary conjunctive grammars.
• Conjunctive grammars and systems of language equations
• On the closure properties of linear conjunctive languages.
• Real-time language recognition by one-dimensional cellular automata
• Systolic trellis automata: Stability, decidability and complexity
• Systolic trellis automatat†
• Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
• One-way bounded cellular automata
• On the Succinctness of Different Representations of Languages
• On the equivalence of linear conjunctive grammars and trellis automata
• The undecidability of the ambiguity problem for minimal linear grammars