Polynomial Time-Bounded Alternating Multi-Counter Automata
スポンサーリンク
概要
- 論文の詳細を見る
An alternating multi-counter automaton (amca) is a generalization of a nondeterministic multi-counter automaton (nmca). The state set of an amca is partitioned into universal and existential states. Greibach showed in Ref. 1) several important properties of nmca's which have polynomial space and operate in polynomial time. In this paper, from a theoretical interest, we investigate a few fundamental properties of polynomial time-bounded amca's. We show, for example ; that (1) there is a language accepted by a two-way deterministic 1-counter automaton operating in linear time, but not accepted by any one-way amca with only universal states operating in polynomial time, and (2) there is a language accepted by a two-way alternating 1-counter automaton with only universal (existential) states operating in linear time, but not accepted by any one-way amca operating in real time.
- 徳山工業高等専門学校の論文
- 2004-12-01
著者
-
XU Jianliang
Ocean University of China
-
INOUE Katsushi
Department of Computer Science and Systems Engineering, Faculty of Engineering, Yamaguchi University
-
Inoue Katsushi
Department Of Computer Science And Systems Engineering Faculty Of Engineering Yamaguchi University
-
Inoue K
Department Of Computer Science And Systems Engineering Faculty Of Engineering Yamaguchi University
-
Xu Jianliang
Department Of Computer Science Ocean University Of China
-
Inoue Katsushi
Yamaguchi Univ.
-
Yoshinaga Tsunehiro
Department Of Computer Science And Electronics Engineering Tokuyama College Of Technology
-
Yoshinaga Tsunehiro
Department Of Computer Science And Electronic Engineering Tokuyama College Of Technology
-
TAKESHIGE Kazue
Yamaguchi Agricultural Cooperative Association Electronic Data Processing Center Co., Ltd.
-
YOSHINAGA Tsunehiro
Tokuyama College of Technology
-
Takeshige Kazue
Yamaguchi Agricultural Cooperative Association Electronic Data Processing Center Co. Ltd.
-
Xu Jianliang
Ocean Univ. China Qingdao Chn
関連論文
- A Space Lower-Bound Technique for Three-Dimensional Alternating Turing Machines
- Sublinear Space-Bounded One-Way Self-Verifying Nondeterministic Turing Machines
- Non-closure Property of One-Pebble Turing Machines with Sublogarithmic Space(Discrete Mathematics and Its Applications)
- 空間量が対数以下に制限された存在(全称)状態のみからなる1-インクドット交代チューリングマシンの閉包性について
- Space hierarchies of three-dimensional turing machines
- Some Properties on Input Head Reversal-Bounded Two-Dimensional Turing Machines (Special Issue on Selected Papers from LA Symposium)
- Self-Verifying Nondeterministic and Las Vegas Multihead Finite Automata (Special Section on Discrete Mathematics and Its Applications)
- A Relationship between Two-Way Deterministic One-Counter Automata and One-Pebble Deterministic Turing Machines with Sublogarithmic Space
- Alternating Rebound Turing Machines (Special Section on Discrete Mathematics and Its Applications)
- Some Observations Concerning Alternating Pushdown Automata with Sublogarithmic Space
- On Multi-Inkdot Two-Way Alternating Turing Machines and Pushdown Automata with Sublogarithmic Space and Constant Leaf-Size
- A Note on Alternating Pushdown Automata With Sublogarithmic Space
- Inkdot versus Pebble over Two-Dimensional Languages
- An algorithm for tower of hanoi with four or more poles
- A note on bottom-up pyramid acceptors
- Video file system
- A modified algorithm for taking reciprocal of n-bit integers
- Non-closure Properties of 1-Inkdot Nondeterministic Turing Machines and Alternating Turing Machines with Only Universal States Using Small Space
- A note on multihead on-line turing machines
- On Simple One-Way Multihead Pushdown Automata
- Sensing Two-Way Three Heads are Better than Two
- A Note on Alternating Multi-Counter Automata with Small Space
- A Note on Realtime One-Way Alternating and Deterministic Multi-Counter Automata(Special Issue on Selected Papers from LA Symposium)
- Las Vegas, Self-Verifying Nondeterministic and Deterministic One-Way Multi-Counter Automata with Bounded Time
- D-1-1 Three-Dimensional Probabilistic Finite Automata
- Three-dimensional multicounter auaomata
- Sublogarithmic Space-Bounded Multi-Inkdot Alternating Turing Machines with Only Existential (Universal) States(Discrete Mathematics and Its Applications)
- Polynomial Time-Bounded Alternating Multi-Counter Automata
- Some Observations on One-way Alternating Pushdown Automata with Sublinear Space(Discrete Mathematics and Its Applications)
- On 1-Inkdot Alternating Pushdown Automata with Sublogarithmic Space(Theory of Automata, Formal Language Theory)
- Some Observations on 1-Inkdot Alternating Multi-Counter Automata with Sublinear Space
- ALTERNATION FOR TWO-WAY (INKDOT) MULTI-COUNTER AUTOMATA WITH SUBLINEAR SPACE
- A leaf-size hierarchy of three-dimensional alternating turing Machines
- A note on decision problems for three-way two-dimensional finite automata
- Sublinear Space-Bounded Multi-Inkdot Alternating Multi-Counter Automata with Only Universal States
- D-1-4 A Relationship between the Accepting Powers of Nondeterministic Finite Automata and Probabilistic Finite Automata on Three-Dimensional Input Tapes
- D-1-3 Non-Closure Properties of Cooperating Systems of One-Way Alternating Finite Automata with Only Universal States