Reversible flowchart languages and the structured reversible program theorem

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Many irreversible computation models have reversible counterparts, but these are poorly understood at present. We introduce reversible flowcharts with an assertion operator and show that any reversible flowchart can be simulated by a structured reversible flowchart using only three control flow operators. Reversible flowcharts are r- Turing-complete, meaning that they can simuluate reversible Turing machines without garbage data. We also demonstrate the injectivization of classical flowcharts into reversible flowcharts. The reversible flowchart computation model provides a theoretical justification for low-level machine code for reversible microprocessors as well as high-level block-structured reversible languages. We give examples for both such languages and illustrate them with a lossless encoder for permutations given by Dijkstra.
OriginalsprogEngelsk
TitelAutomata, Languages and Programming : 35th International colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings. Part II
RedaktørerL. Aceto, I. Damgaard, L. A. Goldberg, M. M. Halldorsson, A. Ingolfsdottir, I. Walukiewicz
ForlagSpringer
Publikationsdato2008
Sider258-270
DOI
StatusUdgivet - 2008
BegivenhedInternational Colloquium on Automata, Languages and Programming 2008 - Reykjavik, Island
Varighed: 7 jul. 200811 jul. 2008
Konferencens nummer: 35

Konference

KonferenceInternational Colloquium on Automata, Languages and Programming 2008
Nummer35
LandIsland
ByReykjavik
Periode07/07/200811/07/2008
NavnLecture notes in computer science
Nummer5126
ISSN0302-9743

Bibliografisk note

http://dx.doi.org/10.1007/978-3-540-70583-3_22

ID: 6363159