Skip to main content

Research Repository

Advanced Search

Memoryless computation: New results, constructions, and extensions

Gadouleau, Maximilien; Riis, Søren

Memoryless computation: New results, constructions, and extensions Thumbnail


Authors

Søren Riis



Abstract

In this paper, we are interested in memoryless computation, a modern paradigm to compute functions which generalises the famous XOR swap algorithm to exchange the contents of two variables without using a buffer. In memoryless computation, programs are only allowed to update one variable at a time. We first consider programs which do not use any memory. We study the maximum and average number of updates required to compute functions without memory. We then derive the exact number of instructions required to compute any manipulation of variables. This shows that combining variables, instead of simply moving them around, not only allows for memoryless programs, but also yields shorter programs. Second, we show that allowing programs to use memory is also incorporated in the memoryless computation framework. We then quantify the gains obtained by using memory: this leads to shorter programs and allows us to use only binary instructions, which is not sufficient in general when no memory is used.

Citation

Gadouleau, M., & Riis, S. (2015). Memoryless computation: New results, constructions, and extensions. Theoretical Computer Science, 562, 129-145. https://doi.org/10.1016/j.tcs.2014.09.040

Journal Article Type Article
Acceptance Date Sep 18, 2014
Online Publication Date Sep 28, 2014
Publication Date Jan 11, 2015
Deposit Date Oct 14, 2015
Publicly Available Date Mar 28, 2024
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 562
Pages 129-145
DOI https://doi.org/10.1016/j.tcs.2014.09.040
Keywords Memoryless computation, Models of computation, Computational difficulty, Symmetric group, Theory of data, Combinatorics.

Files





You might also like



Downloadable Citations