کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952189 1442019 2017 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The complexity of counting quantifiers on equality languages
ترجمه فارسی عنوان
پیچیدگی شمارش کوانتیزرها بر زبانهای برابری
کلمات کلیدی
محدودیت های تعیین شده، شمارش کوانتیزرها، رضایت محدود، زبان برابری، پیچیدگی محاسباتی،
ترجمه چکیده
یک زبان برابری یک ساختار رابطه ای با دامنه بی نهایت است که روابط آن در برابری قابل تعریف اولویت است. ما ضمیمه های مساله رضایت محدودیت های اندازه گیری را بر زبان های برابر برابر می کنیم که در آن کوانتیزاسیون های بومی موجود و جهانی به وسیله بعضی از زیرمجموعه های کوانتسنج شمارش افزوده می شوند. در انجام این کار، ما خود را در دنیای های مختلف قرار می دهیم که در آن دوگانگی ها و سهگانگی ها وجود دارد.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
پیچیدگی شمارش کوانتیزرها بر زبانهای برابری
چکیده انگلیسی
An equality language is a relational structure with infinite domain whose relations are first-order definable in equality. We classify the extensions of the quantified constraint satisfaction problem over equality languages in which the native existential and universal quantifiers are augmented by some subset of counting quantifiers. In doing this, we find ourselves in various worlds in which dichotomies or trichotomies subsist.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 670, 29 March 2017, Pages 56-67
نویسندگان
, , ,