Optimizing reversible simulation of injective functions
Research output: Contribution to journal › Conference article › Research › peer-review
Standard
Optimizing reversible simulation of injective functions. / Yokoyama, Tetsuo; Axelsen, Holger Bock; Glück, Robert.
In: Journal of Multiple-Valued Logic and Soft Computing, Vol. 18, No. 1, 2012, p. 5-24.Research output: Contribution to journal › Conference article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
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
VL - 18
SP - 5
EP - 24
JO - Journal of Multiple-Valued Logic and Soft Computing
JF - Journal of Multiple-Valued Logic and Soft Computing
SN - 1542-3980
IS - 1
Y2 - 2 July 2010 through 3 July 2010
ER -
ID: 33056656