Presentation | 1995/4/21 A Note on Simple Multihead Pushdown Automata Yue Wang, Masaaki Ichikawa, Katsushi Inoue, Akira Ito, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | Let SPDA(k) be the class of languages recognized by simple one-way k-head pushdown automata. The main result of this paper is that, for every k≥1, SPDA(k)⊊︀SPDA(k+1). This paper also investigates some closure properties of SPDA(k), for each k≥2. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | simple multihead pushdown automaton / one-way machine / hierarchy / Kolmogorov-complexity |
Paper # | |
Date of Issue |
Conference Information | |
Committee | COMP |
---|---|
Conference Date | 1995/4/21(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 Simple Multihead Pushdown Automata |
Sub Title (in English) | |
Keyword(1) | simple multihead pushdown automaton |
Keyword(2) | one-way machine |
Keyword(3) | hierarchy |
Keyword(4) | Kolmogorov-complexity |
1st Author's Name | Yue Wang |
1st Author's Affiliation | Faculty of Engineering, Yamaguchi University() |
2nd Author's Name | Masaaki Ichikawa |
2nd Author's Affiliation | Faculty of Engineering, Yamaguchi University |
3rd Author's Name | Katsushi Inoue |
3rd Author's Affiliation | Faculty of Engineering, Yamaguchi University |
4th Author's Name | Akira Ito |
4th Author's Affiliation | Faculty of Engineering, Yamaguchi University |
Date | 1995/4/21 |
Paper # | |
Volume (vol) | vol.95 |
Number (no) | 13 |
Page | pp.pp.- |
#Pages | 6 |
Date of Issue |