Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
From MaRDI portal
Publication:3926063
DOI10.1137/0210027zbMath0471.68059OpenAlexW2056382040MaRDI QIDQ3926063
Stephen R. Mahaney, Juris Hartmanis
Publication date: 1981
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/6253
context-sensitive languagestwo-way automatanondeterministic languagesone-way automatadeterministic languageslog n-tape automata
Related Items
Collapsing degrees via strong computation, NL-printable sets and nondeterministic Kolmogorov complexity, Expressing uniformity via oracles, Isomorphisms and 1-L reductions, DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization, Some modifications of auxiliary pushdown automata, The degree structure of 1-L reductions, On languages accepted with simultaneous complexity bounds and their ranking problem, Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines., Complexity theory for splicing systems, Nonuniform complexity and the randomness of certain complete languages, A survey of space complexity, A very hard log-space counting class, Investigations Concerning the Structure of Complete Sets, Non-commutative arithmetic circuits: depth reduction and size lower bounds, Extension complexity of formal languages
