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." />
Nothing Special   »   [go: up one dir, main page]

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

Ken HIGUCHI
Etsuji TOMITA
Mitsuo WAKATSUKI

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

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


Summary: 
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.

open access publishing via