Minimizing garbage size by generating reversible simulations

Tetsuo Yokoyama; Holger Bock Axelsen; Robert Glück

doi:10.1109/ICNC.2012.73

Minimizing garbage size by generating reversible simulations

Tetsuo Yokoyama, Holger Bock Axelsen, Robert Glück

Datalogisk Institut

3 Citationer (Scopus)

Abstract

Reversible simulations can realize any irreversible computation on any r-Turing complete reversible computation model at the expense of additional garbage output. The problem of minimizing the garbage size is an important issue in reversible simulations. We discuss the notion of the minimal garbage size of reversible simulations. Then, we propose a three-stage reversible simulation for minimizing garbage size; the first stage generates specialized irreversible programs, the second translates them into reversible simulations, and the third performs reversible simulation using the generated reversible programs. Two case studies on sorting algorithms suggest that the proposed method generates solutions with minimal garbage size.

Originalsprog	Engelsk
Titel	Proceedings of the 2012 Third International Conference on Networking and Computing (ICNC)
Antal sider	9
Forlag	IEEE
Publikationsdato	2012
Sider	379-387
ISBN (Trykt)	978-1-4673-4624-5
DOI	https://doi.org/10.1109/ICNC.2012.73
Status	Udgivet - 2012
Begivenhed	2012 Third International Conference on Networking and Computing - Naha, Okinawa, Japan Varighed: 5 dec. 2012 → 7 dec. 2012 Konferencens nummer: 3

Konference

Konference	2012 Third International Conference on Networking and Computing
Nummer	3
Land/Område	Japan
By	Naha, Okinawa
Periode	05/12/2012 → 07/12/2012

Adgang til dokumentet

10.1109/ICNC.2012.73

Minimizing Garbage Size by Generating Reversible Simulations Forlagets udgivne version, 216 KB

Citationsformater

@inproceedings{c49ae280de9e449385ffcc0e68901567,

title = "Minimizing garbage size by generating reversible simulations",

abstract = "Reversible simulations can realize any irreversible computation on any r-Turing complete reversible computation model at the expense of additional garbage output. The problem of minimizing the garbage size is an important issue in reversible simulations. We discuss the notion of the minimal garbage size of reversible simulations. Then, we propose a three-stage reversible simulation for minimizing garbage size; the first stage generates specialized irreversible programs, the second translates them into reversible simulations, and the third performs reversible simulation using the generated reversible programs. Two case studies on sorting algorithms suggest that the proposed method generates solutions with minimal garbage size.",

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

year = "2012",

doi = "10.1109/ICNC.2012.73",

language = "English",

isbn = "978-1-4673-4624-5",

pages = "379--387",

booktitle = "Proceedings of the 2012 Third International Conference on Networking and Computing (ICNC)",

publisher = "IEEE",

note = "2012 Third International Conference on Networking and Computing ; Conference date: 05-12-2012 Through 07-12-2012",

}

TY - GEN

T1 - Minimizing garbage size by generating reversible simulations

AU - Yokoyama, Tetsuo

AU - Axelsen, Holger Bock

AU - Glück, Robert

N1 - Conference code: 3

PY - 2012

Y1 - 2012

N2 - Reversible simulations can realize any irreversible computation on any r-Turing complete reversible computation model at the expense of additional garbage output. The problem of minimizing the garbage size is an important issue in reversible simulations. We discuss the notion of the minimal garbage size of reversible simulations. Then, we propose a three-stage reversible simulation for minimizing garbage size; the first stage generates specialized irreversible programs, the second translates them into reversible simulations, and the third performs reversible simulation using the generated reversible programs. Two case studies on sorting algorithms suggest that the proposed method generates solutions with minimal garbage size.

AB - Reversible simulations can realize any irreversible computation on any r-Turing complete reversible computation model at the expense of additional garbage output. The problem of minimizing the garbage size is an important issue in reversible simulations. We discuss the notion of the minimal garbage size of reversible simulations. Then, we propose a three-stage reversible simulation for minimizing garbage size; the first stage generates specialized irreversible programs, the second translates them into reversible simulations, and the third performs reversible simulation using the generated reversible programs. Two case studies on sorting algorithms suggest that the proposed method generates solutions with minimal garbage size.

U2 - 10.1109/ICNC.2012.73

DO - 10.1109/ICNC.2012.73

M3 - Article in proceedings

SN - 978-1-4673-4624-5

SP - 379

EP - 387

BT - Proceedings of the 2012 Third International Conference on Networking and Computing (ICNC)

PB - IEEE

T2 - 2012 Third International Conference on Networking and Computing

Y2 - 5 December 2012 through 7 December 2012

ER -

Minimizing garbage size by generating reversible simulations

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater