@article{oai:ipsj.ixsq.nii.ac.jp:00102894,
 author = {上里, 友弥 and 南出, 靖彦 and Yuya, Uezato and Yasuhiko, Minamide},
 issue = {4},
 journal = {情報処理学会論文誌プログラミング（PRO）},
 month = {Aug},
 note = {本論では，言語が決定性文脈自由言語（DCFL）ではないことを証明するための，決定性プッシュダウンオートマトン（DPDA）に基づく手法を提案する．提案する手法は，計算中でのスタックの高さを特徴付けるもので，以下のようなスタックの変化に対する直感を形式的に扱うことができる：言語{anbncn | n ≧ 1}が何らかのDPDAで受理できたとすると，aの個数とbの個数を比較した結果として，anbnの部分を読み終わった段階のスタックはほとんど空になっているはずである．このとき，続く文字列cnを検査することができない．したがって，この言語はDCFLではない．具体的には，十分に長い繰返し文字列を消費した結果のスタックの内容には繰返し構造があることを示し，繰返し文字列を消費した結果のスタックが一般化順序機械と呼ばれる機械で定義可能であることを示した．この結果を用いて，上の例のようにaの個数とbの個数を比較するためには，スタックがほとんど空にならなければならないことを形式化して示した．, We propose a new technique based on DPDA (deterministic pushdown automata) for proving that a language is not a DCFL (deterministic context-free language). The following intuitive discussion can be conducted in a formal manner by our technique. If {anbncn | n ≧ 1} is accepted by a DPDA, the content of the stack after reading anbn-part of the input should be almost empty because bn is matched against an. Then, the DPDA cannot correctly check the rest of the input, cn. We characterize the content of the stack after reading a sufficiently long repetition of a string and, show that the content of the stack after reading a repeated string is definable by a generalized sequential machine. By using this characterization, we prove that the stack must be almost empty after matching the substring in the input.},
 pages = {8--20},
 title = {スタック長の特徴付けによる言語の非DCFL性証明},
 volume = {7},
 year = {2014}
}