The LBA-problem and the deterministic tape complexity of two-way one-counter languages over a one-letter alphabet

Research paper by Burkhard Monien

Indexed on: 01 Oct '77Published on: 01 Oct '77Published in: Acta Informatica


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).