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 条
  • [21] MULTI-HEADED ONE-WAY AUTOMATA
    NELSON, CG
    NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY, 1976, 23 (04): : A444 - A444
  • [22] Zero-Reachability in Probabilistic Multi-Counter Automata
    Brazdil, Tomas
    Kiefer, Stefan
    Kucera, Antonin
    Novotny, Petr
    Katoen, Joost-Pieter
    PROCEEDINGS OF THE JOINT MEETING OF THE TWENTY-THIRD EACSL ANNUAL CONFERENCE ON COMPUTER SCIENCE LOGIC (CSL) AND THE TWENTY-NINTH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2014,
  • [23] Deterministic One-Way Simulation of Two-Way Deterministic Finite Automata Over Small Alphabets
    Geffert, Viliam
    Okhotin, Alexander
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2024,
  • [24] Deterministic One-Way Simulation of Two-Way Deterministic Finite Automata over Small Alphabets
    Geffert, Viliam
    Okhotin, Alexander
    DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2021, 2021, 13037 : 26 - 37
  • [25] ON ONE-WAY 2-HEAD DETERMINISTIC FINITE STATE AUTOMATA
    HROMKOVIC, J
    COMPUTERS AND ARTIFICIAL INTELLIGENCE, 1985, 4 (06): : 503 - 526
  • [26] Some observations on one-way alternating pushdown automata with sublinear space
    Xu, JL
    Yoshinaga, T
    Inoue, K
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2004, E87A (05): : 1012 - 1019
  • [27] Learning Realtime One-Counter Automata
    Bruyere, Veronique
    Perez, Guillermo A.
    Staquet, Gaetan
    TOOLS AND ALGORITHMS FOR THE CONSTRUCTION AND ANALYSIS OF SYSTEMS, TACAS 2022, PT I, 2022, 13243 : 244 - 262
  • [28] DETERMINISTIC ONE-COUNTER AUTOMATA
    VALIANT, LG
    PATERSON, MS
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1975, 10 (03) : 340 - 350
  • [29] A Note on the P-completeness of Deterministic One-way Stack Language
    Lange, Klaus-Joern
    JOURNAL OF UNIVERSAL COMPUTER SCIENCE, 2010, 16 (05) : 795 - 799
  • [30] THE REDUCTION OF 2-WAY AUTOMATA TO ONE-WAY AUTOMATA
    SHEPHERDSON, JC
    IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1959, 3 (02) : 198 - 200
12345