Computational completeness of equations over sets of natural numbers

Результат исследований: Научные публикации в периодических изданияхстатья

8 Цитирования (Scopus)


Systems of finitely many equations of the form φ( X1,..., Xn)=ψ(X1,...,Xn) are considered, in which the unknowns Xi 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.

Язык оригиналаанглийский
Страницы (с-по)56-94
Число страниц39
ЖурналInformation and Computation
СостояниеОпубликовано - 1 янв 2014

Предметные области Scopus

  • Теоретические компьютерные науки
  • Информационные системы
  • Прикладные компьютерные науки
  • Математика и теория расчета

Fingerprint Подробные сведения о темах исследования «Computational completeness of equations over sets of natural numbers». Вместе они формируют уникальный семантический отпечаток (fingerprint).