Alternating Finite Automata with Counters and Stack-Counters Operating in Realtime
スポンサーリンク
概要
- 論文の詳細を見る
This paper investigates the accepting powers of one-way alternating finite automata with counters and stack-counters (lafacs's) which operate in realtime. (The difference between "counter" and "stack-counter" is that the latter can be entered without the contents being changed, but the former cannot. ) For each k≧0 and l≧0 ((k, l)≠(0, 0)), let 1AFACS(k, l, real) denote the class of sets accepted by realtime one-way alternating finite automata with k counters and l stack-counters, and let 1UFACS (k, l, real) (1NFACS(k, l, real)) denote the class of sets accepted by realtime one-way alternating finite automata with k counters and l stack-counters which have only universal (existential) states. We first investigate a relationship among the accepting powers of realtime lafacs's with only universal states, with only existential states, and with full alternation, and show, for example, that for each k≧0 and l≧0 ((k, l)≠(0, 0)), 1UFACS(k, l, real) ∪ 1NFACS(k, l, real) ⫋ 1AFACS(k, l, real). We then investigate hierarchical properties based on the number of counters and stack-counters, and show, for example, that for each k≧0 and l≧0 ((k, l)≠(0, 0)), and each X∈{U, N}, 1XFACS (k+1, l, real)-1AFACS (k, l, real)≠φ. We finally investigate a relationship between counters and stack-counters, and show, for example, that for each k≧0, l≧0 and m≧1, and each X∈{U, N}, 1XFACS(k, l+m, real)-1AFACS (k+2m-1, l, real) ≠φ.
- 社団法人電子情報通信学会の論文
- 1995-08-25
著者
-
YOSHINAGA Tsunehiro
Department of Computer Science and Electrics Engineering, Tokuyama College of Technology
-
Inoue Katsushi
Faculty Of Engineering Yamaguchi University
-
Yoshinaga Tsunehiro
Department Of Computer Science And Electrics Engineering
-
Yoshinaga Tsunehiro
Department Of Information And Electronics Engineering Tokuyama College Of Technology
関連論文
- Sublinear Space-Bounded One-Way Self-Verifying Nondeterministic Turing Machines
- 空間量が対数以下に制限された存在(全称)状態のみからなる1-インクドット交代チューリングマシンの閉包性について
- A Note on Probabilistic Rebound Automata
- A Note on Alternating Pushdown Automata with Sublogarithmic Space
- A Note on One-way Auxiliary Pushdown Automata
- Non-closure Properties of 1-Inkdot Nondeterministic Turing Machines and Alternating Turing Machines with Only Universal States Using Small Space
- Leaf-Size Bounded Real-Time Synchronized Alternating One-Way Multicounter Machines
- Closure properties of alternating one-way multihead finite automata with constant leaf-sizes
- A Note on Alternating Multi-Counter Automata with Small Space
- Multihead Finite Automata with Markers (Special Section on Discrete Mathematics and Its Applications)
- A Note on One-Way Multicounter Machines and Cooperating Systems of One-Way Finite Automata
- Some Hierarchy Results on Multihead Automata over a One-Letter Alphabet
- Alternating Finite Automata with Counters and Stack-Counters Operating in Realtime
- Hierarchical Properties of Realtime One-Way Alternating Multi-Stack-Counter Automata (Special Section on Discrete Mathematics and Its Applications)
- A Note on Realtime One-Way Alternating and Deterministic Multi-Counter Automata(Special Issue on Selected Papers from LA Symposium)
- Three-Dimensionally Fully Space Constructible Functions
- Las Vegas, Self-Verifying Nondeterministic and Deterministic One-Way Multi-Counter Automata with Bounded Time
- Sublogarithmic Space-Bounded Multi-Inkdot Alternating Turing Machines with Only Existential (Universal) States(Discrete Mathematics and Its Applications)
- 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)
- Sublinear Space-Bounded Multi-Inkdot Alternating Multi-Counter Automata with Only Universal States