A structural approach to reversible computation

DOI10.1016/J.TCS.2005.07.002MaRDI QIDQ2581367zbMATH OpenOpenAlexWikidataFDO

Authors Samson Abramsky

Publication date 10 January 2006

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

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

zbMATH Keywords

Automata Geometry of Interaction Linear combinatory algebra Reversible computation Term-rewriting

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Abstract: Reversibility is a key issue in the interface between computation and physics, and of growing importance as miniaturization progresses towards its physical limits. Most foundational work on reversible computing to date has focussed on simulations of low-level machine models. By contrast, we develop a more structural approach. We show how high-level functional programs can be mapped compositionally (i.e. in a syntax-directed fashion) into a simple kind of automata which are immediately seen to be reversible. The size of the automaton is linear in the size of the functional term. In mathematical terms, we are building a concrete model of functional computation. This construction stems directly from ideas arising in Geometry of Interaction and Linear Logic---but can be understood without any knowledge of these topics. In fact, it serves as an excellent introduction to them. At the same time, an interesting logical delineation between reversible and irreversible forms of computation emerges from our analysis.

Recommendations

Cites work

Cited in

(40)

Describes a project that uses

Uses Software

ML

This page was built for publication: A structural approach to reversible computation

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