コンテンツメニュー

A leaf-size hierarchy of three-dimensional alternating turing Machines

Technology reports of the Yamaguchi University Volume 5 Issue 5 Page 367-382
published_at 1996-12
KJ00004351187.pdf
[fulltext] 863 KB
Title
A leaf-size hierarchy of three-dimensional alternating turing Machines
Creators Sakamoto Makoto
Creators Inoue Katsushi
Creators Ito Akira
Source Identifiers
Alternating Turing machines were introduced as a generalization of nondeterministic Turing machines and as a mechanism to model parallel computation. ”Leaf-size” (or ”branching”) is the minimum number of leaves of some accepting computation trees of alternating Turing machines. Leaf-size, in a sense, reflects the minimum number of processors that run in parallel in accepting a given input. In this paper, we investigate a hierarchy of complexity classes based on leaf-size bounded computations for three-dimensional alternating Turing machines, and show that for any positive integer k>__-1 and for any two functions L: N→N and L': N→N such that (1) L is a three-dimensionally space-constructible function such that L (m)^<k+1><__- m (m>__-
Subjects
工学 ( Other)
Languages eng
Resource Type departmental bulletin paper
Publishers 山口大学工学部
Date Issued 1996-12
File Version Version of Record
Access Rights open access
Relations
[ISSN]0386-3433
[NCID]AA0086073X
Schools 工学部