Presentation | 2003/7/25 A Note on Rebound Turing Machines Katsushi INOUE, Akira ITO, Takashi KAMIURA, Holger PETERSEN, Ran ZHANG, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | This paper continues the investigation of rebound Turing machines (RTM's). We first investigate a relationship between the accepting powers of simple one-way 2-head finite automata and simultaneously space-bounded and leaf-size bounded alternating RTM's, and show that for any functions L(n) and Z(n) such that L(n)Z(n)=o(log n) and Z(n)=o((log n)/(log log n)), simple one-way 2-head finite automata are incomparable with simultaneously L(n) space-bounded and Z(n) leaf-size bounded alternating RTM's. We then investigate a relationship between Las Vegas and determinism for space-bounded RTM's, and show that there is a language accepted by a Las Vegas rebound automaton, but not accepted by any weakly o(log log n) space-bounded deterministic RTM. This is the first separation result between Las Vegas and determinism for space-bounded computing models over strings. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | space-bounded rebound Turing machine / leaf-size bounded rebound Turing machine / simple one-way 2-head finite automaton / Las Vegas |
Paper # | COMP2003-27 |
Date of Issue |
Conference Information | |
Committee | COMP |
---|---|
Conference Date | 2003/7/25(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Theoretical Foundations of Computing (COMP) |
---|---|
Language | ENG |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | A Note on Rebound Turing Machines |
Sub Title (in English) | |
Keyword(1) | space-bounded rebound Turing machine |
Keyword(2) | leaf-size bounded rebound Turing machine |
Keyword(3) | simple one-way 2-head finite automaton |
Keyword(4) | Las Vegas |
1st Author's Name | Katsushi INOUE |
1st Author's Affiliation | Faculty of Engineering, Yamaguchi University() |
2nd Author's Name | Akira ITO |
2nd Author's Affiliation | Faculty of Engineering, Yamaguchi University |
3rd Author's Name | Takashi KAMIURA |
3rd Author's Affiliation | Faculty of Engineering, Yamaguchi University |
4th Author's Name | Holger PETERSEN |
4th Author's Affiliation | Institut fur Formale Methoden der Informatik, Universitat Stuttgart |
5th Author's Name | Ran ZHANG |
5th Author's Affiliation | Toshiba Corporation e-Solutions Company, System Integration Technology Center |
Date | 2003/7/25 |
Paper # | COMP2003-27 |
Volume (vol) | vol.103 |
Number (no) | 246 |
Page | pp.pp.- |
#Pages | 8 |
Date of Issue |