IEICE TRANSACTIONS on Information
A Polynomial-Time Algorithm for Checking the Inclusion for Real-Time Deterministic Restricted One-Counter Automata Which Accept by Accept Mode
Summary :
A deterministic pushdown automaton (dpda) having just one stack symbol is called a deterministic restricted one-counter automaton (droca). A deterministic one-counter automaton (doca) is a dpda having only one stack symbol, with the exception of a bottom-of-stack marker. The class of languages accepted by droca's which accept by final state is a proper subclass of the class of languages accepted by doca's. Valiant has proved the decidability of the equivalence problem for doca's and the undecidability of the inclusion problem for doca's. Thus the decidability of the equivalence problem for droca's is obvious. In this paper, we evaluate the upper bound of the length of the shortest input string (shortest witness) that disproves the inclusion for a pair of real-time droca's which accept by accept mode, and present a direct branching algorithm for checking the inclusion for a pair of languages accepted by these droca's. Then we show that the worst-case time complexity of our algorithm is polynomial in the size of these droca's.
- Publication
- IEICE TRANSACTIONS on Information Vol.E81-D No.1 pp.1-11
- Publication Date
- 1998/01/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Category
- Automata,Languages 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
Ken HIGUCHI, Mitsuo WAKATSUKI, Etsuji TOMITA, "A Polynomial-Time Algorithm for Checking the Inclusion for Real-Time Deterministic Restricted One-Counter Automata Which Accept by Accept Mode" in IEICE TRANSACTIONS on Information,
vol. E81-D, no. 1, pp. 1-11, January 1998, doi: .
Abstract: A deterministic pushdown automaton (dpda) having just one stack symbol is called a deterministic restricted one-counter automaton (droca). A deterministic one-counter automaton (doca) is a dpda having only one stack symbol, with the exception of a bottom-of-stack marker. The class of languages accepted by droca's which accept by final state is a proper subclass of the class of languages accepted by doca's. Valiant has proved the decidability of the equivalence problem for doca's and the undecidability of the inclusion problem for doca's. Thus the decidability of the equivalence problem for droca's is obvious. In this paper, we evaluate the upper bound of the length of the shortest input string (shortest witness) that disproves the inclusion for a pair of real-time droca's which accept by accept mode, and present a direct branching algorithm for checking the inclusion for a pair of languages accepted by these droca's. Then we show that the worst-case time complexity of our algorithm is polynomial in the size of these droca's.
URL: https://global.ieice.org/en_transactions/information/10.1587/e81-d_1_1/_p
Copy
@ARTICLE{e81-d_1_1,
author={Ken HIGUCHI, Mitsuo WAKATSUKI, Etsuji TOMITA, },
journal={IEICE TRANSACTIONS on Information},
title={A Polynomial-Time Algorithm for Checking the Inclusion for Real-Time Deterministic Restricted One-Counter Automata Which Accept by Accept Mode},
year={1998},
volume={E81-D},
number={1},
pages={1-11},
abstract={A deterministic pushdown automaton (dpda) having just one stack symbol is called a deterministic restricted one-counter automaton (droca). A deterministic one-counter automaton (doca) is a dpda having only one stack symbol, with the exception of a bottom-of-stack marker. The class of languages accepted by droca's which accept by final state is a proper subclass of the class of languages accepted by doca's. Valiant has proved the decidability of the equivalence problem for doca's and the undecidability of the inclusion problem for doca's. Thus the decidability of the equivalence problem for droca's is obvious. In this paper, we evaluate the upper bound of the length of the shortest input string (shortest witness) that disproves the inclusion for a pair of real-time droca's which accept by accept mode, and present a direct branching algorithm for checking the inclusion for a pair of languages accepted by these droca's. Then we show that the worst-case time complexity of our algorithm is polynomial in the size of these droca's.},
keywords={},
doi={},
ISSN={},
month={January},}
Copy
TY - JOUR
TI - A Polynomial-Time Algorithm for Checking the Inclusion for Real-Time Deterministic Restricted One-Counter Automata Which Accept by Accept Mode
T2 - IEICE TRANSACTIONS on Information
SP - 1
EP - 11
AU - Ken HIGUCHI
AU - Mitsuo WAKATSUKI
AU - Etsuji TOMITA
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E81-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 1998
AB - A deterministic pushdown automaton (dpda) having just one stack symbol is called a deterministic restricted one-counter automaton (droca). A deterministic one-counter automaton (doca) is a dpda having only one stack symbol, with the exception of a bottom-of-stack marker. The class of languages accepted by droca's which accept by final state is a proper subclass of the class of languages accepted by doca's. Valiant has proved the decidability of the equivalence problem for doca's and the undecidability of the inclusion problem for doca's. Thus the decidability of the equivalence problem for droca's is obvious. In this paper, we evaluate the upper bound of the length of the shortest input string (shortest witness) that disproves the inclusion for a pair of real-time droca's which accept by accept mode, and present a direct branching algorithm for checking the inclusion for a pair of languages accepted by these droca's. Then we show that the worst-case time complexity of our algorithm is polynomial in the size of these droca's.
ER -
English
