On the number of nonterminals in linear conjunctive grammars

DOI10.1016/J.TCS.2004.03.002MaRDI QIDQ596108zbMATH OpenOpenAlexFDO

Authors 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

automatonCellularConjunctive grammarDescriptional complexityFormal languagesLanguage equationMinimal linear grammarTrellis automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Recommendations

• On the number of nonterminal symbols in unambiguous conjunctive grammars
• On the number of nonterminal symbols in unambiguous conjunctive grammars
• One-nonterminal conjunctive grammars over a unary alphabet
• scientific article; zbMATH DE number 2050924
• scientific article; zbMATH DE number 2201371

Cites work

• scientific article; zbMATH DE number 3426894 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 2040923 (Why is no real title available?)
• scientific article; zbMATH DE number 2068878 (Why is no real title available?)
• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• scientific article; zbMATH DE number 2201371 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• A recognition and parsing algorithm for arbitrary conjunctive grammars.
• Characterizations and computational complexity of systolic trellis automata
• Conjunctive grammars and systems of language equations
• Nonterminal complexity of programmed grammars.
• On real time one-way cellular array
• On real-time cellular automata and trellis automata
• On the Succinctness of Different Representations of Languages
• On the closure properties of linear conjunctive languages.
• On the equivalence of linear conjunctive grammars and trellis automata
• One-way bounded cellular automata
• Real-time language recognition by one-dimensional cellular automata
• Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
• Systolic trellis automata: Stability, decidability and complexity
• Systolic trellis automatat†
• The hardest linear conjunctive language
• The undecidability of the ambiguity problem for minimal linear grammars

Cited in

(9)

• On the number of nonterminal symbols in unambiguous conjunctive grammars
• A CHARACTERIZATION OF THE ARITHMETICAL HIERARCHY BY LANGUAGE EQUATIONS
• Input-driven languages are linear conjunctive
• On the expressive power of univariate equations over sets of natural numbers
• Language equations
• On the number of nonterminal symbols in unambiguous 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
• One-nonterminal conjunctive grammars over a unary alphabet

This page was built for publication: On the number of nonterminals in linear conjunctive grammars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q596108)