Name
Abstract | ||
|---|---|---|
This paper continues the investigation of the fundamental properties of alternating rebound Turing machines (ARTM's). In particular, we shall introduce a simple, natural complexity measure for ARTM's, called "leaf-size", and provide a hierarchy of complexity classes based on leaf-size bounded computations. Leaf-size, in a sense, reflects the number of processors which run in parallel in reading a given input.We show that for any positive integer k ≥ 1 and for any two functions L : N → N ∪ {0} and L' : N → N ∪ {0} such that (i) L is space constructible by a deterministic rebound Turing machine, (ii) L(n)k+1 = o(log n), and (iii) L'(n) = o(L(n)), there exists a language accepted by a strongly L(n) space-bounded and L(n)k leaf-size bounded ARTM, but not accepted by any weakly L(n) space-bounded and L'(n)k leaf-size bounded ARTM.We further show that for any positive integer k ≥ 1, there exists a language accepted by a 2k + 4 leaf-size bounded alternating rebound automaton, but not accepted by any weakly o(log n) space-bounded and k leaf-size bounded ARTM. |
Year | Venue | Keywords |
|---|---|---|
2002 | Journal of Automata, Languages and Combinatorics | natural complexity measure,rebound automaton,deterministic rebound,leaf-size bounded computation,leaf-size hierarchy,weakly l,complexity class,k leaf-size,functions l,log n,positive integer k,computational complexity,turing machine |
Field | DocType | Volume |
Integer,Complexity class,Discrete mathematics,Binary logarithm,Combinatorics,Turing machine,Information complexity,Hierarchy,Mathematics,Bounded function,Computational complexity theory | Journal | 7 |
Issue | Citations | PageRank |
3 | 1 | 0.40 |
References | Authors | |
10 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lan Zhang | 1 | 6 | 1.53 |
| Katsushi Inoue | 2 | 515 | 74.43 |
| Akira Ito | 3 | 1 | 0.40 |
| Yue Wang | 4 | 34 | 9.08 |