Matsuno Hiroshi
Affiliate Master
Yamaguchi University
A note on multihead on-line turing machines
Technology reports of the Yamaguchi University Volume 3 Issue 2
Page 183-192
published_at 1983-12
Title
A note on multihead on-line turing machines
Creators
Sakurayama Shunichi
Creators
Inoue Katsushi
Creators
Takanami Itsuo
Creators
Taniguchi Hiroshi
Source Identifiers
This paper introduces a tape-bounded multihead on-line Turing machine which can be considered as a multihead version of a tape-bounded 1-head on-line Turing machine. We first investigate hierarchies based on the number of input heads. We then investigate the difference between the accepting powers of tape-bounded nondeterministic multihead on-line Turing machines and deterministic ones. Finally, closure properties of the classes of languages accepted by tape-bounded multihead on-line Turing machines are investigated.
Languages
eng
Resource Type
departmental bulletin paper
Publishers
山口大学工学部
Date Issued
1983-12
File Version
Version of Record
Access Rights
open access
Relations
[ISSN]0386-3433
[NCID]AA0086073X
Schools
工学部