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
相关论文
共 50 条
12345