IEICE TRANSACTIONS on Information
Some Properties of Deterministic Restricted One-Counter Automata
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 market. The class of languages accepted by droca's is a proper subclass of the class of languages accepted by doca's. Valiant has shown that the regularity problem for doca's is decidable in a single exponential worst-case time complexity. In this paper, we prove that the class of languages accepted by droca's which accept by final state is incomparable with the class of languages accepted by droca's which accept by empty stack (strict droca's), and that the intersection of them is equal to the class of strict regular languages. In addition, we present a new direct branching algorithm for checking the regularity for not only a strict droca but also a real-time droca which accepts by final state. Then we show that the worst-case time complexity of our algorithm is polynomial in the size of each droca.
- Publication
- IEICE TRANSACTIONS on Information Vol.E79-D No.7 pp.914-924
- Publication Date
- 1996/07/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- 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, "Some Properties of Deterministic Restricted One-Counter Automata" in IEICE TRANSACTIONS on Information,
vol. E79-D, no. 7, pp. 914-924, July 1996, 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 market. The class of languages accepted by droca's is a proper subclass of the class of languages accepted by doca's. Valiant has shown that the regularity problem for doca's is decidable in a single exponential worst-case time complexity. In this paper, we prove that the class of languages accepted by droca's which accept by final state is incomparable with the class of languages accepted by droca's which accept by empty stack (strict droca's), and that the intersection of them is equal to the class of strict regular languages. In addition, we present a new direct branching algorithm for checking the regularity for not only a strict droca but also a real-time droca which accepts by final state. Then we show that the worst-case time complexity of our algorithm is polynomial in the size of each droca.
URL: https://global.ieice.org/en_transactions/information/10.1587/e79-d_7_914/_p
Copy
@ARTICLE{e79-d_7_914,
author={Ken HIGUCHI, Mitsuo WAKATSUKI, Etsuji TOMITA, },
journal={IEICE TRANSACTIONS on Information},
title={Some Properties of Deterministic Restricted One-Counter Automata},
year={1996},
volume={E79-D},
number={7},
pages={914-924},
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 market. The class of languages accepted by droca's is a proper subclass of the class of languages accepted by doca's. Valiant has shown that the regularity problem for doca's is decidable in a single exponential worst-case time complexity. In this paper, we prove that the class of languages accepted by droca's which accept by final state is incomparable with the class of languages accepted by droca's which accept by empty stack (strict droca's), and that the intersection of them is equal to the class of strict regular languages. In addition, we present a new direct branching algorithm for checking the regularity for not only a strict droca but also a real-time droca which accepts by final state. Then we show that the worst-case time complexity of our algorithm is polynomial in the size of each droca.},
keywords={},
doi={},
ISSN={},
month={July},}
Copy
TY - JOUR
TI - Some Properties of Deterministic Restricted One-Counter Automata
T2 - IEICE TRANSACTIONS on Information
SP - 914
EP - 924
AU - Ken HIGUCHI
AU - Mitsuo WAKATSUKI
AU - Etsuji TOMITA
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E79-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 1996
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 market. The class of languages accepted by droca's is a proper subclass of the class of languages accepted by doca's. Valiant has shown that the regularity problem for doca's is decidable in a single exponential worst-case time complexity. In this paper, we prove that the class of languages accepted by droca's which accept by final state is incomparable with the class of languages accepted by droca's which accept by empty stack (strict droca's), and that the intersection of them is equal to the class of strict regular languages. In addition, we present a new direct branching algorithm for checking the regularity for not only a strict droca but also a real-time droca which accepts by final state. Then we show that the worst-case time complexity of our algorithm is polynomial in the size of each droca.
ER -
English
