Unambiguous conjunctive grammars over a one-symbol alphabet

DOI10.1016/J.TCS.2016.12.009MaRDI QIDQ507593zbMATH OpenOpenAlexFDO

Authors Artur Jeż, Alexander Okhotin

Publication date 6 February 2017

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

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

zbMATH Keywords

ambiguityundecidabilitylanguage equationsunary languagesconjunctive grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Cellular automata (computational aspects) (68Q80)

Recommendations

• Unambiguous conjunctive grammars over a one-letter alphabet
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth
• One-Nonterminal Conjunctive Grammars over a Unary Alphabet
• One-nonterminal conjunctive grammars over a unary alphabet

Cites work

• scientific article; zbMATH DE number 3504474 (Why is no real title available?)
• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3415406 (Why is no real title available?)
• Algorithmics on SLP-compressed strings: a survey
• An extension of context-free grammars with one-sided context specifications
• Automatic Sequences
• Boolean grammars
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Characterizations and computational complexity of systolic trellis automata
• Complexity of equations over sets of natural numbers
• Computational completeness of equations over sets of natural numbers
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• Decision problems for language equations
• Homomorphisms preserving linear conjunctive languages
• LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata
• On real time one-way cellular array
• On sparse languages \(L\) such that \(LL= \Sigma^*\)
• On the equivalence of linear conjunctive grammars and trellis automata
• On the expressive power of univariate equations over sets of natural numbers
• One-nonterminal conjunctive grammars over a unary alphabet
• One-way bounded cellular automata
• Parsing Boolean grammars over a one-letter alphabet using online convolution
• Parsing by matrix multiplication generalized to Boolean grammars
• Recognition of linear-slender context-free languages by real time one-way cellular automata
• Systolic trellis automatata †
• The complexity of membership problems for circuits over sets of natural numbers
• Unambiguous Boolean grammars
• Well-founded semantics for Boolean grammars

Cited in

(8)

• Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth
• Conjunctive grammars, cellular automata and logic
• Unambiguous conjunctive grammars over a one-letter alphabet
• Unrestricted complementation in language equations over a one-letter alphabet
• One-Nonterminal Conjunctive Grammars over a Unary Alphabet
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• Formal languages over GF(2)
• Conjunctive Grammars Can Generate Non-regular Unary Languages

This page was built for publication: Unambiguous conjunctive grammars over a one-symbol alphabet

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