کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4662775 1633534 2008 20 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Choiceless polynomial time, counting and the Cai–Fürer–Immerman graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
پیش نمایش صفحه اول مقاله
Choiceless polynomial time, counting and the Cai–Fürer–Immerman graphs
چکیده انگلیسی

We consider Choiceless Polynomial Time (), a language introduced by Blass, Gurevich and Shelah, and show that it can express a query originally constructed by Cai, Fürer and Immerman to separate fixed-point logic with counting () from . This settles a question posed by Blass et al. The program we present uses sets of unbounded finite rank: we demonstrate that this is necessary by showing that the query cannot be computed by any program that has a constant bound on the rank of sets used, even in , an extension of with counting.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 152, Issues 1–3, March 2008, Pages 31-50