WEKO3
-
RootNode
アイテム
スタック長の特徴付けによる言語の非DCFL性証明
https://ipsj.ixsq.nii.ac.jp/records/102894
https://ipsj.ixsq.nii.ac.jp/records/102894f3923b4d-c1f7-449f-b5f5-6c8f77997544
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-TPRO0704003.pdf (567.9 kB)
|
Copyright (c) 2014 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Trans(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2014-08-29 | |||||||
| タイトル | ||||||||
| タイトル | スタック長の特徴付けによる言語の非DCFL性証明 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | A Characterization of Stack for Proofs of Non-DCFL | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | [通常論文] ポンピング補題，プッシュダウンオートマトン，決定性文脈自由言語 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| 筑波大学システム情報工学研究科 | ||||||||
| 著者所属 | ||||||||
| 筑波大学システム情報工学研究科 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science, University of Tsukuba | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science, University of Tsukuba | ||||||||
| 著者名 |
上里, 友弥
南出, 靖彦
× 上里, 友弥 南出, 靖彦
|
|||||||
| 著者名(英) |
Yuya, Uezato
Yasuhiko, Minamide
× Yuya, Uezato Yasuhiko, Minamide
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 本論では，言語が決定性文脈自由言語（DCFL）ではないことを証明するための，決定性プッシュダウンオートマトン（DPDA）に基づく手法を提案する．提案する手法は，計算中でのスタックの高さを特徴付けるもので，以下のようなスタックの変化に対する直感を形式的に扱うことができる：言語{anbncn | n ≧ 1}が何らかのDPDAで受理できたとすると，aの個数とbの個数を比較した結果として，anbnの部分を読み終わった段階のスタックはほとんど空になっているはずである．このとき，続く文字列cnを検査することができない．したがって，この言語はDCFLではない．具体的には，十分に長い繰返し文字列を消費した結果のスタックの内容には繰返し構造があることを示し，繰返し文字列を消費した結果のスタックが一般化順序機械と呼ばれる機械で定義可能であることを示した．この結果を用いて，上の例のようにaの個数とbの個数を比較するためには，スタックがほとんど空にならなければならないことを形式化して示した． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 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. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA11464814 | |||||||
| 書誌情報 |
情報処理学会論文誌プログラミング（PRO） 巻 7, 号 4, p. 8-20, 発行日 2014-08-29 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7802 | |||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
