テセレーションオートマタの様相の複雑さに関する一考察

松村 一夫  丸岡 章  木村 正行  

誌名
電子情報通信学会論文誌 D   Vol.J59-D   No.12   pp.874-880
発行日: 1976/12/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(535.5KB)>>
論文を購入




あらまし: 
山田らは,テセレーションオートマトンの様相の分類を行い,有限様相,周期様相,および準周期様相と呼ばれる様相からなる3つのクラスと,適当なテセレーションオートマトンの全域関数を適用することによりそれぞれこれらのクラスに属する様相になるような様相のクラスを考えた.そして,これらのクラス間の関係を論じ,この6つのクラス及び一様様相と呼ばれる様相のクラスのいずれにも属さない様相のクラスは空ではないことを示した.本論文では,様相の1つの複雑さの尺度を与える関数である系列数関数を定義し,この複雑さの尺度で自明ではない最も簡単な様相からなる集合を分類する.そして,各クラスの特性化を行い,上述の山田らの分類との関連について考察する.そして,自明ではない最も“小さな”系列数関数を有する様相からなるクラスでに含まれるものが存在することを示す.