A time-space tradeoff for language recognition

DOI10.1007/BF01744430zbMath0533.68047OpenAlexW2014131880MaRDI QIDQ3316594

Pavol Ďuriš, Zvi Galil

Publication date: 1984

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01744430

zbMATH Keywords

lower boundslanguage recognitionmultihead automatanondeterministic machine model

Mathematics Subject Classification ID

Related Items (11)

Two time-space tradeoffs for element distinctness ⋮ Tradeoffs for language recognition on alternating machines ⋮ Time-space tradeoffs in algebraic complexity theory ⋮ Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs ⋮ Time-space tradeoffs for SAT on nonuniform machines ⋮ Unnamed Item ⋮ Time-space tradeoffs for satisfiability ⋮ Constant-space, constant-randomness verifiers with arbitrarily small error ⋮ Computing (and Life) Is All about Tradeoffs ⋮ Lower bounds on the complexity of recognizing SAT by Turing machines ⋮ Separation of deterministic, nondeterministic and alternating complexity classes

Cites Work

• A time-space tradeoff for sorting on non-oblivious machines
• Fooling a two way automaton or one pushdown store is better than one counter for two way machines
• Time-space-optimal string matching
• Optimal Arrangement of Keys in a Hash Table

This page was built for publication: A time-space tradeoff for language recognition