Equations over sets of integers with addition only
作者:
Highlights:
• Investigating equations with sets of natural numbers (or any integers) as unknowns.
• The only operation is element-wise addition of sets.
• For natural numbers, these equations are computationally universal.
• For integers, any hyper-arithmetical set can be encoded in a solution.
• Solution existence, uniqueness, etc., are undecidable.
摘要
•Investigating equations with sets of natural numbers (or any integers) as unknowns.•The only operation is element-wise addition of sets.•For natural numbers, these equations are computationally universal.•For integers, any hyper-arithmetical set can be encoded in a solution.•Solution existence, uniqueness, etc., are undecidable.
论文关键词:Language equations,Unary languages,Concatenation,Computability
论文评审过程:Received 18 October 2010, Revised 19 November 2014, Accepted 2 February 2016, Available online 17 March 2016, Version of Record 10 June 2016.
论文官网地址:https://doi.org/10.1016/j.jcss.2016.02.003