Alternate Stacking Technique Revisited: Inclusion Problem of Superdeterministic Pushdown Automata

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 一般社団法人情報処理学会の論文
• 2008-06-26

著者

• Mizuhito Ogawa

  Japan Advanced Institute Of Science And Technology

• Mizuhito Ogawa

  School of Information Science Japan Advanced Institute of Science and Technology

関連論文

• Stacking-based Context-sensitive Points-to Analysis for Java
• On the Inclusion Problem for Context-free Real-time Languages
• Alternate Stacking Technique Revisited: Inclusion Problem of Superdeterministic Pushdown Automata
• Associative Search on Shogi Game Records

スポンサーリンク