Some observations on one-way alternating pushdown automata with sublinear space

被引：0

作者：

Xu, JL

Yoshinaga, T

Inoue, K ^{[1
]}

机构：

[1] Ocean Univ China, Dept Comp Sci, Qingdao 266071, Peoples R China

[2] Tokuyama Coll Technol, Dept Comp Sci & Elect Engn, Tokuyama, Yamaguchi 7458585, Japan

[3] Yamaguchi Univ, Fac Engn, Dept Comp Sci & Syst Engn, Ube, Yamaguchi 7558611, Japan

来源：

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | 2004年 / E87A卷 / 05期

关键词：

alternating pushdown automata; sublogarithmic complexity; sublinear complexity; space hierarchy;

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper investigates some fundamental properties of one-way alternating pushdown automata with sublinear space. We first show that one-way nondeterministic pushdown automata are incomparale with one-way alternating pushdown automata with only universal states, for spaces between log log n and log n, and also for spaces between log n and n/log n. We then show that there exists an infinite space hierarchy among one-way alternating pushdown automata with only universal states which have sublinear space.

引用

页码：1012 / 1019

页数：8

共 12 条

[1] ALTERNATION [J].

CHANDRA, AK ;

KOZEN, DC ;

STOCKMEYER, LJ .

JOURNAL OF THE ACM, 1981, 28 (01) :114-133

[2] SOME OBSERVATIONS CONCERNING ALTERNATING TURING-MACHINES USING SMALL SPACE [J].

CHANG, JH ;

IBARRA, OH ;

RAVIKUMAR, B ;

BERMAN, L .

INFORMATION PROCESSING LETTERS, 1987, 25 (01) :1-9

[3]

GABARRO J, 1984, LECT NOTES COMPUT SC, V166, P250

[4]

INOUE K, 1983, IEICE T E, V66, P395

[5]

ITO A, 1987, IEICE T E, V70, P990

[6] ALTERNATING MULTIHEAD FINITE AUTOMATA [J].

KING, KN .

THEORETICAL COMPUTER SCIENCE, 1988, 61 (2-3) :149-174

[7]

LADER RE, 1978, P 19 IEEE S FDN COMP, P92

[8]

SZEPIETOWSKI A, 1994, LECT NOTES COMPUT SC, V843

[9]

XU J, 1996, COMP9648

[10]

Xu JL, 2003, IEICE T INF SYST, VE86D, P1814

← 1 2 →