Memoryless computation: new results, constructions, and extensions

DOI10.1016/J.TCS.2014.09.040zbMATH Open1303.68057arXiv1111.6026OpenAlexW2963235032MaRDI QIDQ476853FDOQ476853

Authors: Maximilien Gadouleau, Søren Riis 

Publication date: 2 December 2014

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

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.

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

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

zbMATH Keywords

combinatoricssymmetric groupmodels of computationcomputational difficultymemoryless computationtheory of data

Mathematics Subject Classification ID

Cites Work

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

Cited In (15)

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

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)