A1 Refereed original research article in a scientific journal

Computational completeness of equations over sets of natural numbers




AuthorsArtur Jez, Alexander Okhotin

Publication year2014

JournalInformation and Computation

Volume237

First page 56

Last page94

Number of pages39

ISSN0890-5401

DOIhttps://doi.org/10.1016/j.ic.2014.05.001


Abstract

Systems of finitely many equations of the form phi(X-1, ..., X-n) = psi(X-1, ..., X-n) are considered, in which the unknowns X; are sets of natural numbers, while the expressions phi, psi may contain singleton constants and the operations of union and pairwise addition S + T = {m + n vertical bar m is an element of S, n is an element of 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. (C) 2014 Elsevier Inc. All rights reserved.



Last updated on 2024-26-11 at 21:06