Various hierarchies of ω-regular sets

✍ Scribed by Nobuyuki Takahashi

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 582 KB
• Volume: 174
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(96)00245-9

✦ Synopsis

Barua (1992) studied a hierarchy &?,, (n = 1,2,3,. . .), where %?n is a class of w-regular sets which are decomposed into n rational Ga sets forming a decreasing sequence. On the other hand, Kaminski (1985) defined a hierarchy B, (m = 1,2,3,. .), where B, is a class of w-regular sets which are decomposed into 2m rational Ga sets not necessarily forming a decreasing sequence.

We prove that %?zn = B, in spite of the difference of defining conditions. i=l Recently, by applying the resolution theorem of ambiguous sets to 2 (cf. [5, Section 37.111]), Barna [l] constructed a hierarchy of w-regular sets & (n = 1,2,3,. . .). gn+l (n 2 0) is the class of o-languages L satisfying (iv) of the following proposition.