کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950572 | 1440713 | 2017 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The dynamic descriptive complexity of k-clique
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this work the dynamic descriptive complexity of the k-clique query is studied. It is shown that when edges may only be inserted then k-clique can be maintained by a quantifier-free update program of arity kâ1, but it cannot be maintained by a quantifier-free update program of arity kâ2 (even in the presence of unary auxiliary functions). This establishes an arity hierarchy for graph queries for quantifier-free update programs under insertions. The proof of the lower bound uses upper and lower bounds for Ramsey numbers.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 256, October 2017, Pages 9-22
Journal: Information and Computation - Volume 256, October 2017, Pages 9-22
نویسندگان
Thomas Zeume,