Linear Time and Memory-Efficient Computation

DOI10.1137/S0097539793251888MaRDI QIDQ4875449zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(3)

• Partial memoization for obtaining linear time behavior of a 2DPDA
• Memory-tight reductions
• scientific article; zbMATH DE number 6315783 (Why is no real title available?)

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)