Making programs reversible with minimal extra data

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

Making programs reversible with minimal extra data. / Glück, Robert; Yokoyama, Tetsuo.

In: New Generation Computing, Vol. 40, No. 2, 2022, p. 467-480.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Glück, R & Yokoyama, T 2022, 'Making programs reversible with minimal extra data', New Generation Computing, vol. 40, no. 2, pp. 467-480. https://doi.org/10.1007/s00354-022-00169-z

APA

Glück, R., & Yokoyama, T. (2022). Making programs reversible with minimal extra data. New Generation Computing, 40(2), 467-480. https://doi.org/10.1007/s00354-022-00169-z

Vancouver

Glück R, Yokoyama T. Making programs reversible with minimal extra data. New Generation Computing. 2022;40(2):467-480. https://doi.org/10.1007/s00354-022-00169-z

Author

Glück, Robert ; Yokoyama, Tetsuo. / Making programs reversible with minimal extra data. In: New Generation Computing. 2022 ; Vol. 40, No. 2. pp. 467-480.

Bibtex

@article{d898749cfe8c4a679b239027b380975f,
title = "Making programs reversible with minimal extra data",
abstract = "Reversible computing is an unconventional computing paradigm that comes with specific challenges. One of the important questions is the existence of reversible programs with minimal extra output (garbage data). To answer this question for programs that implement partial functions over countable domains, we introduce an order on infinite garbage sets and a notion of minimality. To this end, we present two methods for functions specified by decidable and semi-decidable predicates. Both methods are universal, which means they work for all programs specified by the predicates. They cover Bennett{\textquoteright}s classic input-erasing reversible computation of injective functions. Hence, any program written in a Turing-complete programming language can be implemented with g-minimal garbage in an r-Turing-complete reversible programming language. This generality comes at the cost of a considerable runtime due to the generate-and-test approach.",
keywords = "Garbage data, Injectivization, Reversibilization, Reversible computing, Reversible programming",
author = "Robert Gl{\"u}ck and Tetsuo Yokoyama",
note = "Publisher Copyright: {\textcopyright} 2022, Ohmsha, Ltd. and Springer Japan KK, part of Springer Nature.",
year = "2022",
doi = "10.1007/s00354-022-00169-z",
language = "English",
volume = "40",
pages = "467--480",
journal = "New Generation Computing",
issn = "0288-3635",
publisher = "Springer",
number = "2",

}

RIS

TY - JOUR

T1 - Making programs reversible with minimal extra data

AU - Glück, Robert

AU - Yokoyama, Tetsuo

N1 - Publisher Copyright: © 2022, Ohmsha, Ltd. and Springer Japan KK, part of Springer Nature.

PY - 2022

Y1 - 2022

N2 - Reversible computing is an unconventional computing paradigm that comes with specific challenges. One of the important questions is the existence of reversible programs with minimal extra output (garbage data). To answer this question for programs that implement partial functions over countable domains, we introduce an order on infinite garbage sets and a notion of minimality. To this end, we present two methods for functions specified by decidable and semi-decidable predicates. Both methods are universal, which means they work for all programs specified by the predicates. They cover Bennett’s classic input-erasing reversible computation of injective functions. Hence, any program written in a Turing-complete programming language can be implemented with g-minimal garbage in an r-Turing-complete reversible programming language. This generality comes at the cost of a considerable runtime due to the generate-and-test approach.

AB - Reversible computing is an unconventional computing paradigm that comes with specific challenges. One of the important questions is the existence of reversible programs with minimal extra output (garbage data). To answer this question for programs that implement partial functions over countable domains, we introduce an order on infinite garbage sets and a notion of minimality. To this end, we present two methods for functions specified by decidable and semi-decidable predicates. Both methods are universal, which means they work for all programs specified by the predicates. They cover Bennett’s classic input-erasing reversible computation of injective functions. Hence, any program written in a Turing-complete programming language can be implemented with g-minimal garbage in an r-Turing-complete reversible programming language. This generality comes at the cost of a considerable runtime due to the generate-and-test approach.

KW - Garbage data

KW - Injectivization

KW - Reversibilization

KW - Reversible computing

KW - Reversible programming

U2 - 10.1007/s00354-022-00169-z

DO - 10.1007/s00354-022-00169-z

M3 - Journal article

AN - SCOPUS:85133457724

VL - 40

SP - 467

EP - 480

JO - New Generation Computing

JF - New Generation Computing

SN - 0288-3635

IS - 2

ER -

ID: 314299379