A Fast Algorithm for Checking the Inclusion for Very Simple Deterministic Pushdown Automate
スポンサーリンク
概要
- 論文の詳細を見る
We are concerned with a subclass of deterministic pushdown automata (dpda) called very simple dpda's, and present a new direct branching algorithm for checking the inclusion for a pair of languages accepted by these dpda's. As usual, we take the maximal thickness (i.e., the length of the shortest input strings that make each stack symbol go to empty) of all stack symbols into account as one parameter of the given dpda's. Then the worst-case time complexity of our algorithm is polynomial with respect to these parameters. Without considering the thickness, the complexity is single exponential in the description length of the given dpda's. As far as we are concerned with very simple dpda's, our algorithm is very simple and direct, and is faster and much better than the previously given algorithms for the inclusion problem of dpda's.
- 社団法人電子情報通信学会の論文
- 1993-10-25
著者
-
Tomita Etsuji
Faculty Of Electro-communications The University Of Electro-communications
-
Wakatsuki Mitsuo
Faculty of Electro-Communications, The University of Electro-Communications
-
Wakatsuki Mitsuo
Faculty Of Electro-communications The University Of Electro-communications
関連論文
- A Fast Algorithm for Checking the Inclusion for Very Simple Deterministic Pushdown Automate
- A Polynomial-Time Algorithm for Checking the Inclusion for Real-Time Deterministic Restricted One-Counter Automata Which Accept by Accept Mode
- Some Properties of Deterministic Restricted One-Counter Automata
- A Polynomial-Time Algorithm for Checking the Inclusion for Real-Time Deterministic Restricted One-Counter Automata Which Accept by Final State
- A Polynomial-Time Algorithm for Checking the lnclusion for Strict Deterministic Restricted One-Counter Automata
- Polynomial Time Identification of Strict Deterministic Restricted One-Counter Automata in Some Class from Positive Data