Some properties of deterministic restricted one-counter automata

作     者：Higuchi, K Wakatsuki, M Tomita, E 

作者机构：Faculty of Electro-Communications University of Electro-Communications Chofushi 182 Japan 

出 版 物：《IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS》 (电子信息通信学会汇刊：信息与系统)

年 卷 期：1996年第E79D卷第7期

页      面：914-924页

核心收录：

学科分类：0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：language theory decision algorithm regularity problem deterministic pushdown automaton deterministic restricted one-counter automaton 

摘      要：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 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.