Memoryless computation: new results, constructions, and extensions

DOI10.1016/J.TCS.2014.09.040MaRDI QIDQ476853zbMATH OpenOpenAlexFDO

Authors Maximilien Gadouleau, Søren Riis

Publication date 2 December 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.6026

zbMATH Keywords

combinatoricssymmetric groupmodels of computationcomputational difficultymemoryless computationtheory of data

Mathematics Subject Classification ID

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. This uses a combinatorial framework for procedural programming languages, where programs are only allowed to update one variable at a time. We first consider programs which do not have any memory. We prove that any function of $n$ variables can be computed this way in only $4n-3$ variable updates. 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.

Recommendations

• Computing in permutation groups without memory
• Computing in matrix groups without memory
• Mapping Computation with No Memory
• Computation with no memory, and rearrangeable multicast networks
• Catalytic computation

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 5129494 (Why is no real title available?)
• scientific article; zbMATH DE number 1820639 (Why is no real title available?)
• scientific article; zbMATH DE number 2122440 (Why is no real title available?)
• scientific article; zbMATH DE number 3102822 (Why is no real title available?)
• Association schemes and t-designs in regular semilattices
• Classical finite transformation semigroups. An introduction.
• Closed iterative calculus
• Coding for Errors and Erasures in Random Network Coding
• Combinatorial representations
• Computation with no memory, and rearrangeable multicast networks
• Computing in matrix groups without memory
• Computing in permutation groups without memory
• Elementary decompositions of arbitrary maps over finite sets
• Generalized Connection Networks for Parallel Processor Intercommunication
• Graph theory
• Mapping Computation with No Memory
• Network information flow
• Optimal Rearrangeable Multistage Connecting Networks
• Quadratic sequential computations of Boolean mappings
• Sequential computation of linear Boolean mappings
• Three generators for minimal writing-space computations

Cited in

(15)

• Attractor separation and signed cycles in asynchronous Boolean networks
• Computing in permutation groups without memory
• Computing in matrix groups without memory
• Catalytic computation
• Sequentialization and procedural complexity in automata networks
• Intrinsic universality in automata networks. III: On symmetry versus asynchrony
• Fixing monotone Boolean networks asynchronously
• Intrinsic universality in automata networks. II: Glueing and gadgets
• Mapping Computation with No Memory
• Complete simulation of automata networks
• Synchronizing Boolean networks asynchronously
• scientific article; zbMATH DE number 4179292 (Why is no real title available?)
• On simulation in automata networks
• Strong Turing degrees for additive BSS RAM's
• Computation with no memory, and rearrangeable multicast networks

This page was built for publication: Memoryless computation: new results, constructions, and extensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476853)