A relation between space, return and dual return complexities

DOI10.1016/0304-3975(79)90010-0zbMath0409.68026OpenAlexW2033229895MaRDI QIDQ1259165

Gerd Wechsung, Andreas Brandstädt

Publication date: 1979

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(79)90010-0

zbMATH Keywords

Languages RecognizedReturn ComplexitySpace Complexity of Nondeterministic Turing Machines

Mathematics Subject Classification ID

Related Items (2)

Uniform simulations of nondeterministic real time multitape turing machines ⋮ Descriptional complexity of limited automata

Cites Work

• Writing stack acceptors
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• A generalization of context-free determinism
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A relation between space, return and dual return complexities