On simple one-way multihead pushdown automata

被引：0

作者：

Wang, Y

Inoue, K

Ito, A

机构：

[1] Yamaguchi Univ, Ube-shi, Japan

来源：

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS | 1996年 / E79D卷 / 12期

关键词：

simple multihead pushdown automaton; one-way machine; hierarchy; Kolmogorov complexity;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In [2] Ibarra introduced a restricted Version of one-way muItihead pushdown automaton (PDA), called a simple one-way multihead PDA, and showed that such machines recognize only languages with semilinear property. The main result of this paper is that for each k greater than or equal to 1, simple (sensing) one-way (k+1)-head PDA's are more powerful than simple (sensing) one-way k-head PDA's. This paper also investigates closure properties for simple (sensing) one-way muItihead PDA's.

引用

页码：1613 / 1619

页数：7

共 12 条

[1]

CHEN T, 1988, J COMPUTER SYSTEM SC, V37, P269

[2] HIERARCHIES OF ONE-WAY MULTIHEAD AUTOMATA LANGUAGES [J].