Generating Perfect Reversals of Simple Linear-Codes

Show simple item record

dc.contributor.author Perumalla, Kalyan S.
dc.date.accessioned 2005-03-21T17:44:21Z
dc.date.available 2005-03-21T17:44:21Z
dc.date.issued 2003
dc.identifier.uri http://hdl.handle.net/1853/5922
dc.description.abstract Bi-directional execution - executing forward as well as in reverse - is useful in many contexts. However, traditional techniques for bi-directional execution are not scalable, as they require infinite storage in the presence of "destructive" assignments. We present a new approach that eliminates the scalability problem for bi-directional execution of a class of functions called linear codes, which are sequences of assignments of arbitrary linear expressions to variables. Examples of linear codes include Fibonacci-like sequence generators, and operators such as shift, swap and rotate. We present an algorithm to generate perfect forward-reverse code pair from any given linear code, and show that any linear code can be perfectly inverted despite the presence of destructive assignments and apparent singularities in the input code. While existing techniques require memory size proportional to forward execution length, the code generated by our algorithm uses bounded amount of memory. The memory is proportional only to the number of variables in the given forward code, and is independent of both forward code size and forward execution length. en
dc.format.extent 383335 bytes
dc.format.mimetype application/pdf
dc.language.iso en_US
dc.publisher Georgia Institute of Technology en
dc.relation.ispartofseries CERCS;GIT-CERCS-03-04
dc.subject Algorithms en
dc.subject Bi-directional execution en
dc.subject Destructive assignments en
dc.subject Linear codes en
dc.subject Memory resources en
dc.subject Operators en
dc.subject Scalability en
dc.subject Sequence generators en
dc.subject Variables en
dc.title Generating Perfect Reversals of Simple Linear-Codes en
dc.type Technical Report en


Files in this item

Files Size Format View
git-cercs-03-04.pdf 374.3Kb PDF View/ Open

This item appears in the following Collection(s)

Show simple item record