Four Hierarchies of ω-Regular Languages
スポンサーリンク
概要
- 論文の詳細を見る
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. Already it is reported that B_n=R_<2n> by Takahashi (1995). And besides we show B_n=R_<2n>, where B_n is a class of ω-regular sets whose defining condition is more lenient than that of R_<2n>. In conclusion, we state that various hierarchies are reduced to four types of hierarchies.
- 横浜商科大学の論文
- 1998-03-01
著者
関連論文
- ω-正則集合から成るBarua階層の対称差表現について
- Four Hierarchies of ω-Regular Languages
- An Equivalence between the Kaminski Hierarchy and the Barua Hierarchy
- Kaminski階層とBarua階層との同値性
- On Some Subclasses of the Class of All ω-Star-Free Regular Sets
- ω-star-free minimal setsのLANDWEBERの階層に占める位置について
- Characterization of ω-Type Context-Free Languages by Means of Stack Run
- SM-計算可能性とSM-計算可能関数のクラス
- ω型有限オートマトンについての若干の考察 : BuchiオートマトンとMullerオートマトン(1)
- 有限オートマトンによる実数の定義可能性
- 相対化された多項式時間計算量クラスの細階層について
- SM-計算可能性とSM-計算可能関数のクラス (松本武雄学長喜寿記念号)