A note on decision problems for three-way two-dimensional finite automata
スポンサーリンク
概要
- 論文の詳細を見る
This note investigates some decision problems for three-way two-dimensional finite automata. It is shown, for example, that (1) the emptiness problem for nondeterministic three-way two-dimensional finite automata over a one-letter alphabet is solvable, (2) the universe problem for deterministic three-way two-dimensional finite automata over a one-letter alphabet is solvable, and (3) the universe, containment, and equivalence problems for non-deterministic three-way two-dimensional finite automata are unsolvable.
- 山口大学の論文
著者
-
Inoue Katsushi
Department Of Computer Science And Systems Engineering Faculty Of Engineering Yamaguchi University
-
Inoue Katsushi
Department Of Electronics Faculty Of Engineering Yamaguchi University
-
Takanami Itsuo
Department Of Electronics Engineering
-
Takanami Itsuo
Department Of Electronics Faculty Of Engineering Yamaguchi University
-
INDUE Katsushi
Department of Electronics Faculty of Engineering Yamaguchi University
関連論文
- 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
- 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
- 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
- Learning Algorithms Which Make Multilayer Neural Networks Multiple-Weight-and-Neuron-Fault Tolerant