Dr Maximilien Gadouleau m.r.gadouleau@durham.ac.uk
Associate Professor
Memoryless computation: New results, constructions, and extensions
Gadouleau, Maximilien; Riis, Søren
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 29, 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
Accepted Journal Article
(394 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright Statement
© 2015 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
You might also like
Bent functions in the partial spread class generated by linear recurring sequences
(2022)
Journal Article
Expansive automata networks
(2020)
Journal Article
Fixing monotone Boolean networks asynchronously
(2020)
Journal Article
Elementary, finite and linear vN-regular cellular automata
(2020)
Journal Article
Complete Simulation of Automata Networks
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search