کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426747 | 686259 | 2014 | 39 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Computational completeness of equations over sets of natural numbers
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Computational completeness of equations over sets of natural numbers Computational completeness of equations over sets of natural numbers](/preview/png/426747.png)
چکیده انگلیسی
Systems of finitely many equations of the form φ(X1,…,Xn)=ψ(X1,…,Xn)φ(X1,…,Xn)=ψ(X1,…,Xn) are considered, in which the unknowns XiXi 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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 237, October 2014, Pages 56–94
Journal: Information and Computation - Volume 237, October 2014, Pages 56–94
نویسندگان
Artur Jeż, Alexander Okhotin,