| Presentation | 1995/4/21 A Note on Alternating Pushdown Automata With Sublogarithmic Space Jian-Liang Xu, Katsushi Inoue, Yue Wang, Akira Ito, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | This paper investigates some fundamental properties of alternating one-way (or two-way) pushdown automata (pda's) with sublogarithmic space. We first show that strongly (weakly) sublogarithmic space-bounded two-way alternating pda's are more powerful than one-way alternating pda's with the same space-bound. Then, we show that weakly sublogarithmic space-bounded two-way (one-way) alternating pda's are more powerful than two-way (one-way) nondeterministic pda's and alternating pda's with only universal states using the same space. Futhermore, we investigate several fundamental closure properties, and show that the class of languages accepted by weakly sublogarithmic space-bounded one-way alternating pda's and the class of languages accepted by sublogarithmic space-bounded two-way deterministic pda's (nondeterministic pda's, alternating pda's with only universal states) are not closed under concatenation, Kleene closure, and length preserving homomorphism. Finally, we briefly investigates a relatioship between 'strongly' and 'weakly'. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Alternating Pushdown Automata / sublogarithmic space complexity / one-way versus two-way |
| 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 Alternating Pushdown Automata With Sublogarithmic Space |
| Sub Title (in English) | |
| Keyword(1) | Alternating Pushdown Automata |
| Keyword(2) | sublogarithmic space complexity |
| Keyword(3) | one-way versus two-way |
| 1st Author's Name | Jian-Liang Xu |
| 1st Author's Affiliation | Faculty of Engineering, Yamaguchi University() |
| 2nd Author's Name | Katsushi Inoue |
| 2nd Author's Affiliation | Faculty of Engineering, Yamaguchi University |
| 3rd Author's Name | Yue Wang |
| 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 | 10 |
| Date of Issue | |