Kaminski階層とBarua階層との同値性
スポンサーリンク
概要
- 論文の詳細を見る
ω-regular setを幾つかの正規G_δ集合に分解することを考える.その分解で得られた正規G_δ集合の個数を以て,与えられたω-regular setの複雑性を定める.Barua(1992)はω-regular setの階層R_n(n=1,2,3,…)について,結果を得ている.ここにR_nはω-regular setのクラスであって,そのω-regular setは減少列を形成するn個の正規G_δ集合に分解される,という性質を持っている.一方,Kaminski(1985)は階層B_m(m=1,2,3,…)について考察している.ここにB_mはω-regular setのクラスであって,そのω-regular setは必ずしも減少列を形成しない2m個の正規G_δ集合に分解される,という性質を持っている.この報告では定義の違いにも拘らず,R_2n=B_nが成り立つことを証明する.
- 社団法人電子情報通信学会の論文
- 1995-10-27
著者
関連論文
- ω-正則集合から成る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-計算可能関数のクラス (松本武雄学長喜寿記念号)