WEKO3
アイテム
Alternate Stacking Technique Revisited: Inclusion Problem of Superdeterministic Pushdown Automata
https://ipsj.ixsq.nii.ac.jp/records/16452
https://ipsj.ixsq.nii.ac.jp/records/16452726e92a0-207f-4df1-97a3-9771bcc1b90b
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-TPRO0101005.pdf (314.7 kB)
|
Copyright (c) 2008 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Trans(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2008-06-26 | |||||||
| タイトル | ||||||||
| タイトル | Alternate Stacking Technique Revisited: Inclusion Problem of Superdeterministic Pushdown Automata | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Alternate Stacking Technique Revisited: Inclusion Problem of Superdeterministic Pushdown Automata | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | 通常論文 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| School of Information Science Japan Advanced Institute of Science and Technology | ||||||||
| 著者所属 | ||||||||
| School of Information Science Japan Advanced Institute of Science and Technology | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| School of Information Science, Japan Advanced Institute of Science and Technology | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| School of Information Science, Japan Advanced Institute of Science and Technology | ||||||||
| 著者名 |
NguyenVanTang
Mizuhito, Ogawa
× NguyenVanTang Mizuhito, Ogawa
|
|||||||
| 著者名(英) |
Nguyen, VanTang
Mizuhito, Ogawa
× Nguyen, VanTang Mizuhito, Ogawa
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | This paper refines the alternate stacking technique used in Greibach-Friedman's proof of the language inclusion problem L(A) ⊆ L(B) where A is a pushdown automaton (PDA) and B is a superdeterministic pushdown automaton (SPDA). In particular we propose a product construction of a simulating PDA M whereas the one given by the original proof encoded everything as a stack symbol. This construction avoids the need for the “liveness” condition in the alternate stacking technique and the correctness proof becomes simpler. | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | This paper refines the alternate stacking technique used in Greibach-Friedman's proof of the language inclusion problem L(A) ⊆ L(B), where A is a pushdown automaton (PDA) and B is a superdeterministic pushdown automaton (SPDA). In particular, we propose a product construction of a simulating PDA M, whereas the one given by the original proof encoded everything as a stack symbol. This construction avoids the need for the “liveness” condition in the alternate stacking technique, and the correctness proof becomes simpler. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA11464814 | |||||||
| 書誌情報 |
情報処理学会論文誌プログラミング（PRO） 巻 1, 号 1, p. 36-46, 発行日 2008-06-26 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7802 | |||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
