کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
424424 | 685443 | 2007 | 21 صفحه PDF | دانلود رایگان |
Important examples of classes of functions are the classes of sets (elements of ) which separate a given pair of disjoint r.e. sets: . A wider class consists of the classes of functions which in a generalized sense separate a k-tuple of r.e. sets (not necessarily pairwise disjoint) for each k∈ω: . We study the structure of the Medvedev degrees of such classes and show that the set of degrees realized depends strongly on both k and the extent to which the r.e. sets intersect. Let denote the Medvedev degrees of those Sk(A0,…,Ak−1) such that no m+1 sets among A0,…,Ak−1 have a nonempty intersection. It is shown that each is an upper semi-lattice but not a lattice. The degree of the set of k-ary diagonally nonrecursive functions DNRk is the greatest element of . If 2≤l
Journal: Electronic Notes in Theoretical Computer Science - Volume 167, 24 January 2007, Pages 203-223