Unambiguous conjunctive grammars over a one-symbol alphabet

DOI10.1016/J.TCS.2016.12.009zbMATH Open1356.68121OpenAlexW2568674745MaRDI QIDQ507593FDOQ507593

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

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

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)

Cites Work

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

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)