A Polynomial-Time Algorithm for Checking the Inclusion for Strict Deterministic Restricted One-Counter Automata


IEICE TRANSACTIONS on Information and Systems   Vol.E78-D   No.4   pp.305-313
Publication Date: 1995/04/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Automata, Languages and Theory of Computing
language theory,  decision algorithm,  inclusion problem,  deterministic pushdown automaton,  strict deterministic restricted one-counter automaton,  

Full Text: PDF(677.8KB)>>
Buy this Article

A deterministic pushdown automaton (dpda) having just one stack symbol is called a deterministic restricted one-counter automaton (droca). When it accepts by empty stack, it is called strict. 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 strict droca's is a 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. Hence the decidablity of the equivalence problem for strict droca's is obvious. In this paper, we present a new direct branching algorithm for checking the inclusion for a pair of languages accepted by strict droca's. Then we show that the worst-case time complexity of our algorithm is polynomial with respect to these automata.