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

DOI10.1016/J.IC.2012.01.004MaRDI QIDQ418146zbMATH OpenOpenAlexFDO

Authors Alexander Okhotin, Panos Rondogiannis

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)

Recommendations

• Conjunctive grammars and equations over sets of natural numbers
• scientific article; zbMATH DE number 5906488
• Equations over sets of natural numbers with addition only
• On equations over sets of integers
• On equations over sets of numbers and their limitations

Cites work

• scientific article; zbMATH DE number 3838107 (Why is no real title available?)
• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• scientific article; zbMATH DE number 914352 (Why is no real title available?)
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Decision problems for language equations
• Fast on-line integer multiplication
• Faster integer multiplication
• Language equations with complementation: decision problems
• Language equations with complementation: expressive power
• On language equations with one-sided concatenation
• On the Computational Completeness of Equations over Sets of Natural Numbers
• On the number of nonterminals in linear conjunctive grammars
• Parsing Boolean grammars over a one-letter alphabet using online convolution
• The exceptional set of Goldbach's problem
• The power of commuting with finite sets of words
• Unrestricted complementation in language equations over a one-letter alphabet

Cited in

(14)

• Formal languages over GF(2)
• Language equations
• Computational completeness of equations over sets of natural numbers
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• scientific article; zbMATH DE number 6146470 (Why is no real title available?)
• Representing hyper-arithmetical sets by equations over sets of integers
• One-Nonterminal Conjunctive Grammars over a Unary Alphabet
• One-nonterminal conjunctive grammars over a unary alphabet
• Unambiguous conjunctive grammars over a one-symbol alphabet
• Parsing Boolean grammars over a one-letter alphabet using online convolution
• An extension of context-free grammars with one-sided context specifications
• Conjunctive grammars and equations over sets of natural numbers
• On Equations over Sets of Numbers and Their Limitations
• scientific article; zbMATH DE number 5906488 (Why is no real title available?)

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

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