کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426909 686350 2008 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Generic density and small span theorem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Generic density and small span theorem
چکیده انگلیسی

We refine the genericity concept of Ambos-Spies, by assigning a real number in [0, 1] to every generic set, called its generic density. We construct sets of generic density any E-computable real in [0, 1], and show a relationship between generic density and Lutz resource bounded dimension. We also introduce strong generic density, and show that it is related to packing dimension. We show that all four notions are different. We show that whereas dimension notions depend on the underlying probability measure, generic density does not, which implies that every dimension result proved by generic density arguments, simultaneously holds under any (biased coin based) probability measure. We prove such a result: we improve the small span theorem of Juedes and Lutz, to the packing dimension setting, for k-bounded-truth-table reductions, under any (biased coin) probability measure.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 206, Issue 1, January 2008, Pages 1-14