An Equivalence between the Kaminski Hierarchy and the Barua Hierarchy

概要

論文の詳細を見る
In this paper, we argue several decompositions of ω-regular sets into rational G_δ sets. We measure the complexity of ω-regular sets by the number of rational G_δ sets obtained by the decompositions. Barua (1992) studied a hierarchy R_n (n=1, 2, 3,…), where R_n is a class of ω-regular sets which are decomposed into n rational G_δ sets forming a decreasing sequence. On the other hand, Kaminski (1985) defined a hierarchy B_m (m=1, 2, 3,…), where B_m is a class of ω-regular sets which are decomposed into 2m rational G_δ sets not necessarily forming a decreasing sequence. As a main result, we claim that R_<2n>=B_n in spite of the differences of defining conditions.
横浜商科大学の論文
1996-05-18