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 条
  • [31] One-way reversible multi-head finite automata
    Kutrib, Martin
    Malcher, Andreas
    THEORETICAL COMPUTER SCIENCE, 2017, 682 : 149 - 164
  • [32] A NOTE ON REAL-TIME ONE-WAY ALTERNATING MULTICOUNTER MACHINES
    INOUE, K
    ITO, A
    TAKANAMI, I
    THEORETICAL COMPUTER SCIENCE, 1991, 88 (02) : 287 - 296
  • [33] SUPERIORITY OF ONE-WAY AND REALTIME QUANTUM MACHINES
    Yakaryilmaz, Abuzer
    RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2012, 46 (04): : 615 - 641
  • [34] Shrinking One-Way Cellular Automata
    Kutrib, Martin
    Malcher, Andreas
    Wendlandt, Matthias
    CELLULAR AUTOMATA AND DISCRETE COMPLEX SYSTEMS, AUTOMATA 2015, 2015, 9099 : 141 - 154
  • [35] Fast one-way cellular automata
    Klein, A
    Kutrib, M
    THEORETICAL COMPUTER SCIENCE, 2003, 295 (1-3) : 233 - 250
  • [36] AN EFFECTIVE SIMULATION OF DETERMINISTIC PUSHDOWN-AUTOMATA WITH MANY 2-WAY AND ONE-WAY HEADS
    RYTTER, W
    INFORMATION PROCESSING LETTERS, 1981, 12 (05) : 234 - 236
  • [37] Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata
    Lavado, Giovanna J.
    Pighizzini, Giovanni
    Seki, Shinnosuke
    INFORMATION AND COMPUTATION, 2013, 228 : 1 - 15
  • [38] Shrinking one-way cellular automata
    Martin Kutrib
    Andreas Malcher
    Matthias Wendlandt
    Natural Computing, 2017, 16 : 383 - 396
  • [39] Shrinking one-way cellular automata
    Kutrib, Martin
    Malcher, Andreas
    Wendlandt, Matthias
    NATURAL COMPUTING, 2017, 16 (03) : 383 - 396
  • [40] Complexity of One-Way Cellular Automata
    Kutrib, Martin
    CELLULAR AUTOMATA AND DISCRETE COMPLEX SYSTEMS (AUTOMATA 2014), 2015, 8996 : 3 - 18
12345