کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426487 | 686082 | 2014 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity of two-variable dependence logic and IF-logic
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Complexity of two-variable dependence logic and IF-logic Complexity of two-variable dependence logic and IF-logic](/preview/png/426487.png)
چکیده انگلیسی
We study the two-variable fragments D2D2 and IF2IF2 of dependence logic and independence-friendly logic. We consider the satisfiability and finite satisfiability problems of these logics and show that for D2D2, both problems are NEXPTIME -complete, whereas for IF2IF2, the problems are Π10 and Σ10-complete, respectively. We also show that D2D2 is strictly less expressive than IF2IF2 and that already in D2D2, equicardinality of two unary predicates and infinity can be expressed (the latter in the presence of a constant symbol).This is an extended version of a publication in the proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science (LICS 2011).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 239, December 2014, Pages 237–253
Journal: Information and Computation - Volume 239, December 2014, Pages 237–253
نویسندگان
Juha Kontinen, Antti Kuusisto, Peter Lohmann, Jonni Virtema,