Alternate Stacking Technique Revisited: Inclusion Problem of Superdeterministic Pushdown Automata

情報処理学会 Web Site

この論文をさがす

抄録

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.

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ