The following information was submitted:
Transactions: INTERNATIONAL JOURNAL of COMPUTERS
Transactions ID Number: 19-644
Full Name: Yasuo Uchida
Position: Professor
Age: ON
Sex: Male
Address: 2-14-1, Tokiwadai, Ube City
Country: JAPAN
Tel:
Tel prefix:
Fax:
E-mail address: uchida@ube-k.ac.jp
Other E-mails: yasuo@uchida.ac
Title of the Paper: Path-Bounded Finite Automata on Four-Dimensional Input Tapes
Authors as they appear in the Paper:
Email addresses of all the authors:
Number of paper pages: 8
Abstract: M.Blum and C.Hewitt first proposed two-dimensional automata as a computational model of two-dimensional pattern processing, and investigated their pattern recognition abilities in 1967. Since then, many researchers in this field have been investigating many properties about automata on two- or three-dimensional tapes. By the way, the question of whether processing four-dimensional digital patterns is much difficult than two- or three-dimensional ones is of great interest from the theoretical and practical standpoints. Recently, due to the advances in many application areas such as computer animation, motion image processing, virtual reality systems, and so forth, it has become increasingly apparent that the study of four-dimensional pattern processing has been of crucial importance. Thus, the study of four-dimensional automata, i.e., fourdimensional automata with the time axis as a computational model of four-dimensional pattern processing has also been meaningful.!
On the other hand, the comparative study of the computational powers of deterministic and nondeterministic computations is one of the central tasks of complexity theory. This paper investigates the computational power of nondeterministic computing devices with restricted nondeterminism. There are only few results measuring the computational power of restricted nondeterminism. In general, there are three possibilities to measure the amount of nondeterminism in computation. In this paper, we consider the possibility to count the number of different nondeterministic computation paths on any input. In particular, we deal with seven-way four-dimensional finite automata with multiple input heads operating on four-dimensional input tapes.
Keywords: computational complexity, finite automaton, fourdimension, multihead, path-bounded
EXTENSION of the file: .pdf
Special (Invited) Session: Path-Bounded Four-Dimensional Finite Automata
Organizer of the Session: 635-408
How Did you learn about congress:
IP ADDRESS: 202.18.184.67
