The following information was submitted:
Transactions: WSEAS TRANSACTIONS ON COMPUTERS
Transactions ID Number: 89-448
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: Synchronized Alternating Turing Machines on Four-Dimensional Input Tapes
Authors as they appear in the Paper:
Email addresses of all the authors:
Number of paper pages: 10
Abstract: Synchronized alternating machine is an alternating machine with a special subset of internal states called synchronizing states. This paper introduces a four-dimensional synchronized alternating Turing machine (4-SATM), and investigates fundamental properties of 4-SATMfs. The main topics of this paper are: (1) a relationship between the accepting powers of 4-SATMfs and four-dimensional alternating Turing machines with small space bounds, (2) a relationship between the accepting powers of seven-way and eight-way 4-SATMfs, (3) a relationship between the accepting powers of 4-SATMfs and four-dimensional nondeterministic Turing machines. In this paper, we let each sidelength of each input tape of these automata be equivalent in order to increase the theoretical interest.
Keywords: alternation, computational complexity, configuration, four-dimensional Turing machine, synchronization
EXTENSION of the file: .pdf
Special (Invited) Session: Four-Dimensional Synchronized Alternating Turing Machines
Organizer of the Session: 629-225
How Did you learn about congress:
IP ADDRESS: 202.18.184.67
