کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4662492 | 1633553 | 2006 | 36 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Succinct definitions in the first order theory of graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
منطق ریاضی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We say that a first order sentence A defines a graph G if A is true on G but false on any graph non-isomorphic to G. Let L(G) (resp. D(G)) denote the minimum length (resp. quantifier rank) of such a sentence. We define the succinctness function s(n) (resp. its variant q(n)) to be the minimum L(G) (resp. D(G)) over all graphs on n vertices.We prove that s(n) and q(n) may be so small that for no general recursive function f we can have f(s(n))≥n for all n. However, for the function q∗(n)=maxi≤nq(i), which is the least nondecreasing function bounding q(n) from above, we have q∗(n)=(1+o(1))log∗n, where log∗n equals the minimum number of iterations of the binary logarithm sufficient to lower n to 1 or below.We show an upper bound q(n)
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 139, Issues 1–3, May 2006, Pages 74-109
Journal: Annals of Pure and Applied Logic - Volume 139, Issues 1–3, May 2006, Pages 74-109