On the expressive power of univariate equations over sets of natural numbers

DOI10.1016/j.ic.2012.01.004zbMath1263.68102OpenAlexW2022226854MaRDI QIDQ418146

Panos Rondogiannis, Alexander Okhotin

Publication date: 24 May 2012

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2012.01.004

zbMATH Keywords

language equationsconjunctive grammarssets of natural numbers

Mathematics Subject Classification ID

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

Related Items (10)

Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ One-nonterminal conjunctive grammars over a unary alphabet ⋮ Unambiguous conjunctive grammars over a one-symbol alphabet ⋮ An extension of context-free grammars with one-sided context specifications ⋮ Representing hyper-arithmetical sets by equations over sets of integers ⋮ Parsing Boolean grammars over a one-letter alphabet using online convolution ⋮ Formal languages over GF(2) ⋮ On Equations over Sets of Numbers and Their Limitations ⋮ One-Nonterminal Conjunctive Grammars over a Unary Alphabet ⋮ Language equations

Cites Work

• On the number of nonterminals in linear conjunctive grammars
• Parsing Boolean grammars over a one-letter alphabet using online convolution
• Language equations with complementation: expressive power
• Language equations with complementation: decision problems
• Decision problems for language equations
• Unrestricted complementation in language equations over a one-letter alphabet
• Fast on-line integer multiplication
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• The power of commuting with finite sets of words
• On the Computational Completeness of Equations over Sets of Natural Numbers
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Faster Integer Multiplication
• The exceptional set of Goldbach's problem
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the expressive power of univariate equations over sets of natural numbers