Equations over sets of integers with addition only

DOI10.1016/J.JCSS.2016.02.003MaRDI QIDQ295632zbMATH OpenOpenAlexFDO

Authors Artur Jeż, Alexander Okhotin

Publication date 13 June 2016

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2016.02.003

zbMATH Keywords

computabilityconcatenationlanguage equationsunary languages

Mathematics Subject Classification ID

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

Recommendations

• Equations over sets of natural numbers with addition only
• On equations over sets of integers
• On equations over sets of numbers and their limitations
• Representing hyper-arithmetical sets by equations over sets of integers
• On Equations over Sets of Numbers and Their Limitations

Cites work

• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Additive combinatorics
• Boolean grammars
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Complexity of equations over sets of natural numbers
• Computational completeness of equations over sets of natural numbers
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• Decidability of trajectory-based equations
• Decision problems for language equations
• Language equations with complementation: decision problems
• Language equations with complementation: expressive power
• On equations over sets of numbers and their limitations
• On language equations with invertible operations
• On the equivalence of linear conjunctive grammars and trellis automata
• Representing hyper-arithmetical sets by equations over sets of integers
• The complexity of membership problems for circuits over sets of integers
• The complexity of membership problems for circuits over sets of natural numbers
• The power of commuting with finite sets of words
• Two Families of Languages Related to ALGOL
• Unresolved systems of language equations: expressive power and decision problems
• Unrestricted complementation in language equations over a one-letter alphabet

Cited in

(10)

• Language equations
• Equations \(X + A = B\) and \((X + X) + C = (X - X) + D\) over sets of natural numbers
• On equations over sets of integers
• Equations over sets of natural numbers with addition only
• Least and greatest solutions of equations over sets of integers
• On equations over sets of numbers and their limitations
• Representing hyper-arithmetical sets by equations over sets of integers
• Least and greatest solutions of equations over sets of integers
• On the Computational Completeness of Equations over Sets of Natural Numbers
• On Equations over Sets of Numbers and Their Limitations

Describes a project that uses

Uses Software

• ALGOL 60

This page was built for publication: Equations over sets of integers with addition only

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