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

Department of Computer Science

3 Citations (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.

Original language	English
Title of host publication	Proceedings of the 2012 Third International Conference on Networking and Computing (ICNC)
Number of pages	9
Publisher	IEEE
Publication date	2012
Pages	379-387
ISBN (Print)	978-1-4673-4624-5
DOIs	https://doi.org/10.1109/ICNC.2012.73
Publication status	Published - 2012
Event	2012 Third International Conference on Networking and Computing - Naha, Okinawa, Japan Duration: 5 Dec 2012 → 7 Dec 2012 Conference number: 3

Conference

Conference	2012 Third International Conference on Networking and Computing
Number	3
Country/Territory	Japan
City	Naha, Okinawa
Period	05/12/2012 → 07/12/2012

Access to Document

10.1109/ICNC.2012.73

Minimizing Garbage Size by Generating Reversible Simulations Final published version, 216 KB

Cite this

@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

Conference

Access to Document

Fingerprint

Cite this