Linear Time and Memory-Efficient Computation

DOI10.1137/S0097539793251888zbMATH Open0841.68041OpenAlexW1999665052MaRDI QIDQ4875449FDOQ4875449

Authors: Kenneth W. Regan 

Publication date: 2 July 1996

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539793251888

Recommendations

• scientific article; zbMATH DE number 512978
• On similarity and duality of computation (I)
• scientific article; zbMATH DE number 6292628
• A new model for large memories

zbMATH Keywords

complexity classesTuring machinesfinite automatonrandom-access machines

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (3)

• Memory-tight reductions
• Title not available (Why is that?)
• Partial memoization for obtaining linear time behavior of a 2DPDA

This page was built for publication: Linear Time and Memory-Efficient Computation

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