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

DOI10.1016/J.IC.2012.01.004zbMATH Open1263.68102OpenAlexW2022226854MaRDI QIDQ418146FDOQ418146

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

Recommendations

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

zbMATH Keywords

language equationsconjunctive grammarssets of natural numbers

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

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

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)