کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
423559 | 685256 | 2016 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The Decision Problem for a Three-sorted Fragment of Set Theory with Restricted Quantification and Finite Enumerations
ترجمه فارسی عنوان
مسأله تصمیم گیری برای یک قطعه سه طبقه بندی شده مجموعه نظریه با سنجش کمی محدود و دادههای شمارشی مقادیر شمارشی محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We solve the satisfiability problem for a three-sorted fragment of set theory (denoted ), which admits a restricted form of quantification over individual and set variables and the finite enumeration operator {-,-,...,-} over individual variables, by showing that it enjoys a small model property, i.e., any satisfiable formula ψ of has a finite model whose size depends solely on the length of ψ itself. Several set-theoretic constructs are expressible by -formulae, such as some variants of the power set operator and the unordered Cartesian product. In particular, concerning the latter construct, we show that when finite enumerations are allowed, the resulting formula is exponentially shorter than in their absence.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 322, 18 April 2016, Pages 69-86
Journal: Electronic Notes in Theoretical Computer Science - Volume 322, 18 April 2016, Pages 69-86