部分関数を定義するm-n列変換器の性質

林 雄二  

誌名
電子情報通信学会論文誌 D   Vol.J77-D1   No.6   pp.409-414
発行日: 1994/06/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: オートマン,言語理論,計算論
キーワード: 
列変換器,  列関数,  決定問題,  部分関数,  閉包性,  

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




あらまし: 
m-n列変換器は,m本の入力テープ,n本の出力テープをもつ有限状態機械である.特に,これが部分関数を定義する場合はm-n列関数と言い,データを並列的に操作するプログラムのモデルとして有効である.我々は,m-n列関数のもつ種々の性質,すなわち(1)集合演算の下での閉包性,(2)等価性判定などの決定問題,を1-1列関数の場合と対比しながら考察した.特に,m-n列変換器がm-n列関数を定義するか否かの問題が決定不能であることを証明している.1-1列変換器についてはこの問題が決定可能であることがBlattner(1977)などによって示されているので,この結果は1-1列変換器とm-n列変換器の性質の違いを示す特徴的なものである.