@article{Jez201456,
    Abstract = {Abstract Systems of finitely many equations of the form φ ( X 1 , {\ldots} , X n ) = ψ ( X 1 , {\ldots} , X n ) are considered, in which the unknowns X i are sets of natural numbers, while the expressions φ , ψ may contain singleton constants and the operations of union and pairwise addition S + T = { m + n | m ∈ S , n ∈ T } . It is shown that the family of sets representable by unique (least, greatest) solutions of such systems is exactly the family of recursive (r.e., co-r.e., respectively) sets of numbers. Basic decision problems for these systems are located in the arithmetical hierarchy. The same results are established for equations with addition and intersection.},
    Author = {Je{\.z}, Artur and Okhotin, Alexander},
    File = {Computational completeness of equations over sets of natural numbers - Jeż, Okhotin (0) (0) - a - a - h.pdf},
    ISSN = {0890-5401},
    Journal = {Information and Computation},
    Keywords = {Computability},
    Number = {0},
    Pages = {56 - 94},
    Title = {Computational completeness of equations over sets of natural numbers},
    URL = {http://www.sciencedirect.com/science/article/pii/S0890540114000637},
    Volume = {237},
    Year = {2014},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0890540114000637},
    bdsk-url-2 = {http://dx.doi.org/10.1016/j.ic.2014.05.001},
    date-added = {2014-12-30 10:14:59 +0000},
    date-modified = {2014-12-30 10:14:59 +0000},
    doi = {10.1016/j.ic.2014.05.001}
}

@article{Jez201456, Abstract = {Abstract Systems of finitely many equations of the form φ ( X 1 , {\ldots} , X n ) = ψ ( X 1 , {\ldots} , X n ) are considered, in which the unknowns X i are sets of natural numbers, while the expressions φ , ψ may contain singleton constants and the operations of union and pairwise addition S + T = { m + n | m ∈ S , n ∈ T } . It is shown that the family of sets representable by unique (least, greatest) solutions of such systems is exactly the family of recursive (r.e., co-r.e., respectively) sets of numbers. Basic decision problems for these systems are located in the arithmetical hierarchy. The same results are established for equations with addition and intersection.}, Author = {Je{.z}, Artur and Okhotin, Alexander}, File = {Computational completeness of equations over sets of natural numbers - Jeż, Okhotin (0) (0) - a - a - h.pdf}, ISSN = {0890-5401}, Journal = {Information and Computation}, Keywords = {Computability}, Number = {0}, Pages = {56 - 94}, Title = {Computational completeness of equations over sets of natural numbers}, URL = {http://www.sciencedirect.com/science/article/pii/S0890540114000637}, Volume = {237}, Year = {2014}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0890540114000637}, bdsk-url-2 = {http://dx.doi.org/10.1016/j.ic.2014.05.001}, date-added = {2014-12-30 10:14:59 +0000}, date-modified = {2014-12-30 10:14:59 +0000}, doi = {10.1016/j.ic.2014.05.001} }