IEICE TRANSACTIONS on Information
A Fast Algorithm for Checking the Inclusion for Very Simple Deterministic Pushdown Automata
Summary :
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 empry) 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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E76-D No.10 pp.1224-1233
- Publication Date
- 1993/10/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Automaton, Language and Theory of Computing
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Mitsuo WAKATSUKI, Etsuji TOMITA, "A Fast Algorithm for Checking the Inclusion for Very Simple Deterministic Pushdown Automata" in IEICE TRANSACTIONS on Information,
vol. E76-D, no. 10, pp. 1224-1233, October 1993, doi: .
Abstract: 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 empry) 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e76-d_10_1224/_p
Copy
@ARTICLE{e76-d_10_1224,
author={Mitsuo WAKATSUKI, Etsuji TOMITA, },
journal={IEICE TRANSACTIONS on Information},
title={A Fast Algorithm for Checking the Inclusion for Very Simple Deterministic Pushdown Automata},
year={1993},
volume={E76-D},
number={10},
pages={1224-1233},
abstract={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 empry) 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.},
keywords={},
doi={},
ISSN={},
month={October},}
Copy
TY - JOUR
TI - A Fast Algorithm for Checking the Inclusion for Very Simple Deterministic Pushdown Automata
T2 - IEICE TRANSACTIONS on Information
SP - 1224
EP - 1233
AU - Mitsuo WAKATSUKI
AU - Etsuji TOMITA
PY - 1993
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E76-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 1993
AB - 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 empry) 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.
ER -
English
