動作等価性によるプログラム形の能力比較について

二木 厚吉  木村 正行  

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


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




あらまし: 
本論文では,プログラムが出力を出すまでに行う基本関数および基本判定の適用の系列まで考慮した動作等価性に基づき,幾つかのプログラム形のクラスの能力が比較されている.まず色々なプログラム形にマーカを使う能力を付加する影響が,次に使用が許されるプッシュダウンストア(pds)の数に制限を付ける影響が調べられる.その結果,有限個の変数の使用だけが許される単純プログラム形のクラス以外ではマーカの使用を許すことで能力が上がること,空判定ができないpdsの使用では,任意の自然数nに対しn+1個のpdsの使用が許されたプログラム形のクラスがn個の使用が許されるものよりも能力が大きいことが示される.これらの結果は,プログラムの入出力関係だけに注目した強等価性に基づいては多くの場合においてマーカの使用は能力を上げず,又空判定ができないpdsの使用は2個で任意個をシミュレートできるという,既に知られている結果に対比するものである.