On the Computational Completeness of Equations over Sets of Natural Numbers

DOI10.1007/978-3-540-70583-3_6zbMath1155.03309OpenAlexW1560143702MaRDI QIDQ3520304

Artur Jeż, Alexander Okhotin

Publication date: 19 August 2008

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-70583-3_6

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items (10)

Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ On the expressive power of univariate equations over sets of natural numbers ⋮ One-nonterminal conjunctive grammars over a unary alphabet ⋮ Functions Definable by Arithmetic Circuits ⋮ Representing hyper-arithmetical sets by equations over sets of integers ⋮ Conjunctive grammars with restricted disjunction ⋮ Conjunctive Grammars with Restricted Disjunction ⋮ On Equations over Sets of Numbers and Their Limitations ⋮ One-Nonterminal Conjunctive Grammars over a Unary Alphabet ⋮ Language equations with complementation: expressive power

This page was built for publication: On the Computational Completeness of Equations over Sets of Natural Numbers