Equations over sets of integers with addition only

DOI10.1016/J.JCSS.2016.02.003zbMATH Open1342.68185OpenAlexW2311082201MaRDI QIDQ295632FDOQ295632

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

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

zbMATH Keywords

computabilityconcatenationlanguage equationsunary languages

Mathematics Subject Classification ID

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

Cites Work

• Additive combinatorics
• Title not available (Why is that?)
• 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
• On language equations with invertible operations
• Boolean grammars
• Computational completeness of equations over sets of natural numbers
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• The complexity of membership problems for circuits over sets of natural numbers
• Decidability of trajectory-based equations
• On equations over sets of numbers and their limitations
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Title not available (Why is that?)
• On the equivalence of linear conjunctive grammars and trellis automata
• Two Families of Languages Related to ALGOL
• Complexity of equations over sets of natural numbers
• Representing hyper-arithmetical sets by equations over sets of integers
• Language equations with complementation: expressive power
• Unresolved systems of language equations: expressive power and decision problems
• The complexity of membership problems for circuits over sets of integers
• Language equations with complementation: decision problems
• Decision problems for language equations

Cited In (10)

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

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)