シンプルマルチヘッドオートマタに関するある性質

井上 克司  中村 昭  阿江 忠  高浪 五男  

誌名
電子情報通信学会論文誌 D   Vol.J60-D   No.9   pp.742-749
発行日: 1977/09/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


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




あらまし: 
最近,Ibarraらによって,マルチヘッドオートマタ(MHA)の制限されたタイプであるシンプルマルチヘッドオートマタ(SPMHA)が導入され,その二,三の性質が明らかにされた.SPMHAは,用いられるヘッドのうちの1つのみがテープ上の記号を識別でき,ほかのヘッドはテープの左,右の境界記号以外はテープ上の記号を識別することのできないようなMHAである.本稿の目的は,SPMHAで受理される言語族の性質を更に詳細に調べることである.SPMHAの言語受理能力が,(1)用いられるヘッドの個数,(2)動作の決定性と非決定性,(3)検知機能の有無(任意の2つのヘッドが同一のコマ上にあるか否かを検知する機能の有無),などによっていかに異なってくるか,又SPMHAの受理する言語族の種々の演算の下での閉包性はいかであるかなどについて検討する.