Fernando Martinez, Juntao Chen, et al.
AAAI 2025
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.
Fernando Martinez, Juntao Chen, et al.
AAAI 2025
David W. Jacobs, Daphna Weinshall, et al.
IEEE Transactions on Pattern Analysis and Machine Intelligence
David Cash, Dennis Hofheinz, et al.
Journal of Cryptology
Renu Tewari, Richard P. King, et al.
IS&T/SPIE Electronic Imaging 1996