Contents Menu

A Note on the ε-Move of On-Line Multitape Turing Machines

Memoirs of the Faculty of Engineering, Yamaguchi University Volume 31 Issue 1 Page 83-87
published_at 1980
KJ00000156337.pdf
[fulltext] 370 KB
Title
オンライン多テープチューリング機械のε-動作に関する一考察
A Note on the ε-Move of On-Line Multitape Turing Machines
Creators Inoue Katsushi
Creators Takanami Itsuo
Source Identifiers
Let f (n) be a time function. By k-DTM (f (n)) (k-NTM (f (n))), we denote the class of languages accepted by deterministic (nondeterministic) on-line k-tape Turing machines which, given an input of length n, operate in such a way that the input heads stay on the same input position at most f (n) steps. This paper shows that if lim [f (n)/(log n)^r]=0 for some positive constant r, then (1) [numerical formula] and [numerical formula], and (2) [numerical formula] and [numerical formula] are not closed under concatenation, Kleene closure, length-preserving homomorphism, or reversal.
Subjects
電気電子工学 ( Other)
Languages jpn
Resource Type departmental bulletin paper
Publishers 山口大学工学部
Date Issued 1980
File Version Version of Record
Access Rights open access
Relations
[ISSN]0372-7661
[NCID]AN00244228
Schools 工学部