@article{JEZ20161007,
    Abstract = {Systems of equations of the form X=Y+Z and X=C are considered, in which the unknowns are sets of integers, the plus operator denotes element-wise sum of sets, and C is an ultimately periodic constant. For natural numbers, such equations are equivalent to language equations over a one-symbol alphabet using concatenation and regular constants. It is shown that such systems are computationally universal: for every recursive (r.e., co-r.e.) set S⊆N there exists a system with a unique (least, greatest) solution containing a component T with S={n|16n+13∈T}. Testing solution existence for these equations is Π10-complete, solution uniqueness is Π20-complete, and finiteness of the set of solutions is Σ30-complete. A similar construction for integers represents any hyper-arithmetical set S⊆Z by a set T⊆Z satisfying S={n|16n∈T}, whereas testing solution existence is Σ11-complete.},
    Author = {Je{\.z}, Artur and Okhotin, Alexander},
    File = {1-s2.0-S0022000016000131-main - a - a - i.pdf},
    ISSN = {0022-0000},
    Journal = {Journal of Computer and System Sciences},
    Keywords = {Language equations, Unary languages, Concatenation, Computability},
    Number = {6},
    Pages = {1007 - 1019},
    Title = {Equations over sets of integers with addition only},
    URL = {http://www.sciencedirect.com/science/article/pii/S0022000016000131},
    Volume = {82},
    Year = {2016},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0022000016000131},
    bdsk-url-2 = {https://doi.org/10.1016/j.jcss.2016.02.003},
    date-added = {2019-08-08 11:08:14 +0200},
    date-modified = {2019-08-08 11:08:14 +0200},
    doi = {10.1016/j.jcss.2016.02.003}
}

@article{JEZ20161007, Abstract = {Systems of equations of the form X=Y+Z and X=C are considered, in which the unknowns are sets of integers, the plus operator denotes element-wise sum of sets, and C is an ultimately periodic constant. For natural numbers, such equations are equivalent to language equations over a one-symbol alphabet using concatenation and regular constants. It is shown that such systems are computationally universal: for every recursive (r.e., co-r.e.) set S⊆N there exists a system with a unique (least, greatest) solution containing a component T with S={n|16n+13∈T}. Testing solution existence for these equations is Π10-complete, solution uniqueness is Π20-complete, and finiteness of the set of solutions is Σ30-complete. A similar construction for integers represents any hyper-arithmetical set S⊆Z by a set T⊆Z satisfying S={n|16n∈T}, whereas testing solution existence is Σ11-complete.}, Author = {Je{.z}, Artur and Okhotin, Alexander}, File = {1-s2.0-S0022000016000131-main - a - a - i.pdf}, ISSN = {0022-0000}, Journal = {Journal of Computer and System Sciences}, Keywords = {Language equations, Unary languages, Concatenation, Computability}, Number = {6}, Pages = {1007 - 1019}, Title = {Equations over sets of integers with addition only}, URL = {http://www.sciencedirect.com/science/article/pii/S0022000016000131}, Volume = {82}, Year = {2016}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0022000016000131}, bdsk-url-2 = {https://doi.org/10.1016/j.jcss.2016.02.003}, date-added = {2019-08-08 11:08:14 +0200}, date-modified = {2019-08-08 11:08:14 +0200}, doi = {10.1016/j.jcss.2016.02.003} }