Three-Way Two-Dimensional Deterministic Finite Automata with Rotated Inputs(<Special Section>Foundations of Computer Science)
スポンサーリンク
概要
- 論文の詳細を見る
Inoue et al. introduced an automaton on a two-dimensional tape, which decides acceptance or rejection of an input tape by scanning the tape from various sides by various automata which move one way, and investigated the accepting power of such an automaton. This paper continues the investigation of this type of automata, especially, v-type automata (obtained by combining four three-way two-dimensional deterministic finite automata (tr2-dfa's) in "or" fashion) and ∧-type automata (obtained by combining four tr2-dfa's in "and" fashion). We first investigate a relationship between the accepting powers of ∨-type automata and ∧-type automata, and show that they are incomparable. Then, we investigate a hierarchy of the accepting powers based on the number of tr2-dfa's combined. Finally, we briefly describe a relationship between the accepting powers of automata obtained by combining three-way two-dimensional deterministic and nondeterministic finite automata.
- 社団法人電子情報通信学会の論文
- 2005-01-01
著者
-
Inoue Katsushi
The Department Of Computer Science And Systems Engineering Faculty Of Engineering Yamaguchi Universi
-
ITO Akira
the Department of Computer Science and Systems Engineering, Faculty of Engineering, Yamaguchi Univer
-
Ito Akira
The Department Of Computer Science And Systems Engineering Faculty Of Engineering Yamaguchi Universi
-
HIRAKAWA Hisao
Hitachi Software Engineering Ltd.
関連論文
- Path-Bounded One-Way Multihead Finite Automata(Foundations of Computer Science)
- 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 Note on Sensing Semi-One-Way Simple Multihead Finite Automata (Special lssue on Selected Papers from LA Synposium)
- 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)
- On the Sensing Function of One-Way Simple Multihead Finite Automata
- A Note on Probabilistic Rebound Automata
- 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
- A Note on One-way Auxiliary Pushdown Automata
- A Note on Alternating Pushdown Automata With Sublogarithmic Space
- A Linear-Time Normalization of One-Dimensional Quadtrees
- On Simple One-Way Multihead Pushdown Automata
- Sensing Two-Way Three Heads are Better than Two
- Neurocysticercosis without Detectable Specific Antibody
- Three-Way Two-Dimensional Deterministic Finite Automata with Rotated Inputs(Foundations of Computer Science)
- Some Observations on 1-Inkdot Alternating Multi-Counter Automata with Sublinear Space
- Inherited Heterozygous Protein C Deficiency and Dysfunctional Protein S with Recurrent Venous Thrombotic Diseases. A Study of Three Generations of a Japanese Family.