Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata

DOI10.1137/0210027MaRDI QIDQ3926063zbMATH OpenOpenAlexFDO

Authors Stephen R. Mahaney, J. 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

zbMATH Keywords

context-sensitive languagesdeterministic languageslog n-tape automatanondeterministic languagesone-way automatatwo-way automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited in

(17)

• Isomorphisms and 1-L reductions
• Nonuniform complexity and the randomness of certain complete languages
• A survey of space complexity
• A very hard log-space counting class
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Expressing uniformity via oracles
• DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization
• Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
• Collapsing degrees via strong computation
• NL-printable sets and nondeterministic Kolmogorov complexity
• Complexity theory for splicing systems
• Investigations concerning the structure of complete sets
• Some modifications of auxiliary pushdown automata
• The degree structure of 1-L reductions
• On languages accepted with simultaneous complexity bounds and their ranking problem
• Regular expressions with backreferences and lookaheads capture NLOG
• Extension complexity of formal languages

This page was built for publication: Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3926063)