A note on realtime one-way alternating and deterministic multi-counter automata

被引：0

作者：

Yoshinaga, T ^{[1
]}

Inoue, K

机构：

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

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

来源：

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS | 2002年 / E85D卷 / 02期

关键词：

alternating multi-counter automata; deterministic multi-counter automata; one-way computation; realtime computation; computational complexity;

D O I：

暂无

中图分类号：

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

学科分类号：

0812 ;

摘要：

This paper investigates the accepting powers of one-way alternating and deterministic multi-counter automata operating in realtime. We partially solve the open problem posed in [4], and show that for each k greater than or equal to 1. there is a language accepted by a realtune one-way deterministic (k + 3)-counter automaton, but not accepted by any realtime one-way alternating k-counter automaton.

引用

页码：346 / 349

页数：4

共 7 条

[1]

Book R., 1972, Mathematical Systems Theory, V6, P37, DOI 10.1007/BF01706072

[2] ALTERNATION [J].

CHANDRA, AK ;

KOZEN, DC ;

STOCKMEYER, LJ .

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

[3]

FISHER PC, 1968, MATH SYST THEORY, V2, P265

[4]

Hopcroft J.E., 1969, Formal Languages and Their Relation To Automata

[5] A NOTE ON REAL-TIME ONE-WAY ALTERNATING MULTICOUNTER MACHINES [J].

INOUE, K ;

ITO, A ;

TAKANAMI, I .

THEORETICAL COMPUTER SCIENCE, 1991, 88 (02) :287-296

[6]

YOSHINAGA T, 1994, IEICE T FUND ELECTR, VE77A, P621

[7]

YOSHINAGA T, 1995, IEICE T INF SYST, VE78D, P929

← 1 →