Optimizing reversible simulation of injective functions

Research output: Contribution to journalConference articleResearchpeer-review

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.
Original languageEnglish
JournalJournal of Multiple-Valued Logic and Soft Computing
Volume18
Issue number1
Pages (from-to)5-24
Number of pages20
ISSN1542-3980
Publication statusPublished - 2012
Event2nd Workshop on Reversible Computing - Bremen, Germany
Duration: 2 Jul 20103 Jul 2010

Conference

Conference2nd Workshop on Reversible Computing
CountryGermany
CityBremen
Period02/07/201003/07/2010

Bibliographical note

Special issue: reversible computation

ID: 33056656