上昇型プッシュダウン木オートマトンと下降型プッシュダウン木オートマトンの受理能力の比較について

概要

論文の詳細を見る
プッシュダウン木オートマトン (PDTA) は互いに双対概念をなす下降型 (t-PDTA) と上昇型 (b-PDTA) の二つの形がある.このうち, b-PDTA は1985年 K.M.Schimpf らによって初めて導入され, t-PDTA と受理能力が同じであることが示された^9).しかしながら,そこで導入された概念は t-PDTA の概念と同じで,その理論的意義は極めて低いものである.これに対して,1989年山崎により K.M.Schimpf らとは異なる b-PDTA が導入されその基本的性質が示された^15).本論文は,このような背景のもとで,山崎によって提案された b-PDTA と t-PDTA の受理能力の比較を行っている.主な内容を述べると,(1)任意の単一状態 lsb-PDTA M に対して N(M')=N(M) となる lst-PDTA M' が常に存在する,(2) t-PDTA で受理されるが b-PDTA で受理不能な木言語が存在する,そしてこの結果(3) b-PDTA で受理される木言語のクラスが t-PDTA で受理される木言語のクラスに真に包含されることが示されている.
一般社団法人情報処理学会の論文
1991-09-15