Reversible flowchart languages and the structured reversible program theorem

Tetsuo Yokoyama; Holger Bock Axelsen; Robert Glück

doi:10.1007/978-3-540-70583-3_22

Reversible flowchart languages and the structured reversible program theorem

Tetsuo Yokoyama, Holger Bock Axelsen, Robert Glück

Department of Computer Science

29 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Automata, Languages and Programming : 35th International colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings. Part II
Editors	L. Aceto, I. Damgaard, L. A. Goldberg, M. M. Halldorsson, A. Ingolfsdottir, I. Walukiewicz
Publisher	Springer
Publication date	2008
Pages	258-270
DOIs	https://doi.org/10.1007/978-3-540-70583-3_22
Publication status	Published - 2008
Event	International Colloquium on Automata, Languages and Programming 2008 - Reykjavik, Iceland Duration: 7 Jul 2008 → 11 Jul 2008 Conference number: 35

Conference

Conference	International Colloquium on Automata, Languages and Programming 2008
Number	35
Country/Territory	Iceland
City	Reykjavik
Period	07/07/2008 → 11/07/2008

Series	Lecture notes in computer science
Number	5126
ISSN	0302-9743

Access to Document

10.1007/978-3-540-70583-3_22

Cite this

Yokoyama, T., Axelsen, H. B., & Glück, R. (2008). Reversible flowchart languages and the structured reversible program theorem. In L. Aceto, I. Damgaard, L. A. Goldberg, M. M. Halldorsson, A. Ingolfsdottir, & I. Walukiewicz (Eds.), Automata, Languages and Programming: 35th International colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings. Part II (pp. 258-270). Springer. https://doi.org/10.1007/978-3-540-70583-3_22

Reversible flowchart languages and the structured reversible program theorem. / Yokoyama, Tetsuo; Axelsen, Holger Bock; Glück, Robert.
Automata, Languages and Programming: 35th International colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings. Part II. ed. / L. Aceto; I. Damgaard; L. A. Goldberg; M. M. Halldorsson; A. Ingolfsdottir; I. Walukiewicz. Springer, 2008. p. 258-270 (Lecture notes in computer science; No. 5126).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Yokoyama, T, Axelsen, HB & Glück, R 2008, Reversible flowchart languages and the structured reversible program theorem. in L Aceto, I Damgaard, LA Goldberg, MM Halldorsson, A Ingolfsdottir & I Walukiewicz (eds), Automata, Languages and Programming: 35th International colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings. Part II. Springer, Lecture notes in computer science, no. 5126, pp. 258-270, International Colloquium on Automata, Languages and Programming 2008, Reykjavik, Iceland, 07/07/2008. https://doi.org/10.1007/978-3-540-70583-3_22

Yokoyama T, Axelsen HB, Glück R. Reversible flowchart languages and the structured reversible program theorem. In Aceto L, Damgaard I, Goldberg LA, Halldorsson MM, Ingolfsdottir A, Walukiewicz I, editors, Automata, Languages and Programming: 35th International colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings. Part II. Springer. 2008. p. 258-270. (Lecture notes in computer science; No. 5126). doi: 10.1007/978-3-540-70583-3_22

Yokoyama, Tetsuo ; Axelsen, Holger Bock ; Glück, Robert. / Reversible flowchart languages and the structured reversible program theorem. Automata, Languages and Programming: 35th International colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings. Part II. editor / L. Aceto ; I. Damgaard ; L. A. Goldberg ; M. M. Halldorsson ; A. Ingolfsdottir ; I. Walukiewicz. Springer, 2008. pp. 258-270 (Lecture notes in computer science; No. 5126).

@inproceedings{f05553b08ffb11dd86a6000ea68e967b,

title = "Reversible flowchart languages and the structured reversible program theorem",

abstract = "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. ",

author = "Tetsuo Yokoyama and Axelsen, {Holger Bock} and Robert Gl{\"u}ck",

note = "http://dx.doi.org/10.1007/978-3-540-70583-3_22; International Colloquium on Automata, Languages and Programming 2008 ; Conference date: 07-07-2008 Through 11-07-2008",

year = "2008",

doi = "10.1007/978-3-540-70583-3_22",

language = "English",

series = "Lecture notes in computer science",

publisher = "Springer",

number = "5126",

pages = "258--270",

editor = "L. Aceto and I. Damgaard and Goldberg, {L. A.} and Halldorsson, {M. M.} and A. Ingolfsdottir and I. Walukiewicz",

booktitle = "Automata, Languages and Programming",

}

TY - GEN

T1 - Reversible flowchart languages and the structured reversible program theorem

AU - Yokoyama, Tetsuo

AU - Axelsen, Holger Bock

AU - Glück, Robert

N1 - Conference code: 35

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-540-70583-3_22

DO - 10.1007/978-3-540-70583-3_22

M3 - Article in proceedings

T3 - Lecture notes in computer science

SP - 258

EP - 270

BT - Automata, Languages and Programming

A2 - Aceto, L.

A2 - Damgaard, I.

A2 - Goldberg, L. A.

A2 - Halldorsson, M. M.

A2 - Ingolfsdottir, A.

A2 - Walukiewicz, I.

PB - Springer

T2 - International Colloquium on Automata, Languages and Programming 2008

Y2 - 7 July 2008 through 11 July 2008

ER -

Reversible flowchart languages and the structured reversible program theorem

Abstract

Conference

Access to Document

Fingerprint

Cite this