Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
A new formal model of register machines is described. Registers contain bit vectorswhich are manipulated using bitwise Boolean operations and shifts. Our main results relate the language recognition power of such vector machines to that of Turing machines. A class of vector machines is exhibited for which time on a vector machine supplies, to within a polynomial, just as much power as space on a Turing machine. Moreover, this is true regardless of whether the machines are deterministic or non-deterministic. © 1976 Academic Press, Inc.
Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
Imran Nasim, Melanie Weber
SCML 2024
David W. Jacobs, Daphna Weinshall, et al.
IEEE Transactions on Pattern Analysis and Machine Intelligence
Martin Charles Golumbic, Renu C. Laskar
Discrete Applied Mathematics