Optimizing reversible simulation of injective functions

Tetsuo Yokoyama; Holger Bock Axelsen; Robert Glück

Optimizing reversible simulation of injective functions

Tetsuo Yokoyama, Holger Bock Axelsen, Robert Glück

Datalogisk Institut

8 Citationer (Scopus)

Abstract

Bennett showed that a clean reversible simulation of injective programs is possible without returning the input of a program as additional output. His method involves two computation and two uncomputation phases. This paper proposes an optimization of Bennett’s simulation that requires only half of the computation and uncomputation steps for a class of injective programs. A practical consequence is that the reversible simulation runs twice as fast as Bennett’s simulation. The proposed method is demonstrated by developing lossless encoders and decoders for run-length encoding and range coding. The range-coding program is further optimized by conserving the model over the text-generation phase. This paper may thus provide a newviewon developing efficient reversible simulations for a certain class of injective functions.

Originalsprog	Engelsk
Tidsskrift	Journal of Multiple-Valued Logic and Soft Computing
Vol/bind	18
Udgave nummer	1
Sider (fra-til)	5-24
Antal sider	20
ISSN	1542-3980
Status	Udgivet - 2012
Begivenhed	2nd Workshop on Reversible Computing - Bremen, Tyskland Varighed: 2 jul. 2010 → 3 jul. 2010

Konference

Konference	2nd Workshop on Reversible Computing
Land/Område	Tyskland
By	Bremen
Periode	02/07/2010 → 03/07/2010

Adgang til dokumentet

http://www.oldcitypublishing.com/journals/mvlsc-home/mvlsc-issue-contents/mvlsc-volume-18-number-1-2012/mvlsc-18-1-p-5-24/

Citationsformater

@inproceedings{2bb589bef7f449fcab97ab40e1a0fe6b,

title = "Optimizing reversible simulation of injective functions",

abstract = "Bennett showed that a clean reversible simulation of injective programs is possible without returning the input of a program as additional output. His method involves two computation and two uncomputation phases. This paper proposes an optimization of Bennett{\textquoteright}s simulation that requires only half of the computation and uncomputation steps for a class of injective programs. A practical consequence is that the reversible simulation runs twice as fast as Bennett{\textquoteright}s simulation. The proposed method is demonstrated by developing lossless encoders and decoders for run-length encoding and range coding. The range-coding program is further optimized by conserving the model over the text-generation phase. This paper may thus provide a newviewon developing efficient reversible simulations for a certain class of injective functions.",

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

note = "Special issue: reversible computation; 2nd Workshop on Reversible Computing ; Conference date: 02-07-2010 Through 03-07-2010",

year = "2012",

language = "English",

volume = "18",

pages = "5--24",

journal = "Journal of Multiple-Valued Logic and Soft Computing",

issn = "1542-3980",

publisher = "Old City Publishing, Inc.",

number = "1",

}

TY - GEN

T1 - Optimizing reversible simulation of injective functions

AU - Yokoyama, Tetsuo

AU - Axelsen, Holger Bock

AU - Glück, Robert

N1 - Special issue: reversible computation

PY - 2012

Y1 - 2012

N2 - Bennett showed that a clean reversible simulation of injective programs is possible without returning the input of a program as additional output. His method involves two computation and two uncomputation phases. This paper proposes an optimization of Bennett’s simulation that requires only half of the computation and uncomputation steps for a class of injective programs. A practical consequence is that the reversible simulation runs twice as fast as Bennett’s simulation. The proposed method is demonstrated by developing lossless encoders and decoders for run-length encoding and range coding. The range-coding program is further optimized by conserving the model over the text-generation phase. This paper may thus provide a newviewon developing efficient reversible simulations for a certain class of injective functions.

AB - Bennett showed that a clean reversible simulation of injective programs is possible without returning the input of a program as additional output. His method involves two computation and two uncomputation phases. This paper proposes an optimization of Bennett’s simulation that requires only half of the computation and uncomputation steps for a class of injective programs. A practical consequence is that the reversible simulation runs twice as fast as Bennett’s simulation. The proposed method is demonstrated by developing lossless encoders and decoders for run-length encoding and range coding. The range-coding program is further optimized by conserving the model over the text-generation phase. This paper may thus provide a newviewon developing efficient reversible simulations for a certain class of injective functions.

M3 - Conference article

SN - 1542-3980

VL - 18

SP - 5

EP - 24

JO - Journal of Multiple-Valued Logic and Soft Computing

JF - Journal of Multiple-Valued Logic and Soft Computing

IS - 1

T2 - 2nd Workshop on Reversible Computing

Y2 - 2 July 2010 through 3 July 2010

ER -

Optimizing reversible simulation of injective functions

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater