ON THE EQUIVALENCE OF TWO-WAY PUSHDOWN AUTOMATA AND COUNTER MACHINES OVER BOUNDED LANGUAGES

作     者：OSCAR H. IBARRA TAO JIANG NICHOLAS TRAN HUI WANG 

作者机构：Department of Computer Science University of California Santa Barbara CA 93106. Research supported in part by NSF Grants CCR89–18403 and CCR90–96221. Department of Computer Science and Systems McMaster University Hamilton Ontario L8S 4K1 Canada. Research supported in part by NSERC Operating Grant OGP 0046613. Department of Computer Science University of Alabama in Huntsville Huntsville AL 35899. 

出 版 物：《International Journal of Foundations of Computer Science》 

年 卷 期：1993年第4卷第2期

页      面：135-146页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Counter Machine Emptiness Problem Pushdown Automaton Reversal-Bounded 

摘      要：It is known that two-way pushdown automata are more powerful than two-way counter machines. The result is also true for the case when the pushdown store and counter are reversal-bounded. In contrast, we show that two-way reversal-bounded push-down automata over bounded languages (i.e., subsets of for some distinct symbols a 1 ,…, a k ) are equivalent to two-way reversal-bounded counter machines. We also show that, unlike the unbounded input case, two-way reversal-bounded pushdown automata over bounded languages have decidable emptiness, equivalence and containment problems.