The LBA-problem and the deterministic tape complexity of two-way one-counter languages over a one-letter alphabet |
| |
| Authors: | Burkhard Monien |
| |
| Affiliation: | 1. Abteilung Informatik der Universit?t, Postfach 500500, D-4600, Dortmund 50, Germany (Fed. Rep.)
|
| |
| Abstract: | Summary It is shown, that NTAPE(n) is equal to TAPE(n) if and only if every language L⊂⊣{1}*⊢ which is acceptable by a nondeterministic two-way one-counter automaton whose counter length is bounded by the length of its input is contained in TAPE(log n). |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
