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

Datalogisk Institut

29 Citationer (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.

Originalsprog	Engelsk
Titel	Automata, Languages and Programming : 35th International colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings. Part II
Redaktører	L. Aceto, I. Damgaard, L. A. Goldberg, M. M. Halldorsson, A. Ingolfsdottir, I. Walukiewicz
Forlag	Springer
Publikationsdato	2008
Sider	258-270
DOI	https://doi.org/10.1007/978-3-540-70583-3_22
Status	Udgivet - 2008
Begivenhed	International Colloquium on Automata, Languages and Programming 2008 - Reykjavik, Island Varighed: 7 jul. 2008 → 11 jul. 2008 Konferencens nummer: 35

Konference

Konference	International Colloquium on Automata, Languages and Programming 2008
Nummer	35
Land/Område	Island
By	Reykjavik
Periode	07/07/2008 → 11/07/2008

Navn	Lecture notes in computer science
Nummer	5126
ISSN	0302-9743

Adgang til dokumentet

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

Citationsformater

Yokoyama, T., Axelsen, H. B., & Glück, R. (2008). Reversible flowchart languages and the structured reversible program theorem. I L. Aceto, I. Damgaard, L. A. Goldberg, M. M. Halldorsson, A. Ingolfsdottir, & I. Walukiewicz (red.), Automata, Languages and Programming: 35th International colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings. Part II (s. 258-270). Springer. Lecture notes in computer science Nr. 5126 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. red. / L. Aceto; I. Damgaard; L. A. Goldberg; M. M. Halldorsson; A. Ingolfsdottir; I. Walukiewicz. Springer, 2008. s. 258-270 (Lecture notes in computer science; Nr. 5126).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Yokoyama, T, Axelsen, HB & Glück, R 2008, Reversible flowchart languages and the structured reversible program theorem. i L Aceto, I Damgaard, LA Goldberg, MM Halldorsson, A Ingolfsdottir & I Walukiewicz (red), Automata, Languages and Programming: 35th International colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings. Part II. Springer, Lecture notes in computer science, nr. 5126, s. 258-270, International Colloquium on Automata, Languages and Programming 2008, Reykjavik, Island, 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. I Aceto L, Damgaard I, Goldberg LA, Halldorsson MM, Ingolfsdottir A, Walukiewicz I, red., Automata, Languages and Programming: 35th International colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings. Part II. Springer. 2008. s. 258-270. (Lecture notes in computer science; Nr. 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. red. / L. Aceto ; I. Damgaard ; L. A. Goldberg ; M. M. Halldorsson ; A. Ingolfsdottir ; I. Walukiewicz. Springer, 2008. s. 258-270 (Lecture notes in computer science; Nr. 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

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater