2026-05-20T20:32:44Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00016452 2025-01-22T23:51:32Z 934:935:938:941

Alternate Stacking Technique Revisited: Inclusion Problem of Superdeterministic Pushdown Automata Alternate Stacking Technique Revisited: Inclusion Problem of Superdeterministic Pushdown Automata NguyenVanTang Mizuhito, Ogawa Nguyen, VanTang Mizuhito, Ogawa 通常論文 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. 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. journal article 情報処理学会 2008-06-26 application/pdf 情報処理学会論文誌プログラミング（PRO） 1 1 36 46 1882-7802 AA11464814 https://ipsj.ixsq.nii.ac.jp/record/16452/files/IPSJ-TPRO0101005.pdf eng