Some Properties of Deterministic Restricted One-Counter Automata

Ken HIGUCHI; Mitsuo WAKATSUKI; Etsuji TOMITA

Some Properties of Deterministic Restricted One-Counter Automata

Ken HIGUCHI, Mitsuo WAKATSUKI, Etsuji TOMITA

Full Text Views

0

Share
Cite this

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

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://globals.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 -