Quantcast

Transformational methods and their application to complexity problems

Research paper by Burkhard Monien

Indexed on: 01 Mar '76Published on: 01 Mar '76Published in: Acta Informatica



Abstract

NTAPE (log n)=TAPE (log n)⇔There exists a j such that every language accepted by a nondeterministic one-way one-counter automaton is contained in Dj. (Dj is the family of all languages accepted by deterministic j-head two-way finite automata.)NTAPE (n) =TAPE (n)⇔ There exists a j such that every language L ∉ {1}* accepted by a nondeterministic 5-head two-way finite automaton is contained in Dj.\(\mathop U\limits_d\) TIME (nd=TAPE (log n)⇔ There exists a j such that every language accepted by a deterministic 1-head two-way pushdown automaton is contained in Dj.f\(\mathop U\limits_d\) TIME (dn)=TAPE (n)⇔There exists a j such that every language L ⊂{1}* accepted by a deterministic 1-head two-way pushdown automaton is contained in Dj.Dj ≨ Dj+1 for all j ε εN.