Show simple item record

dc.contributor.authorPerumalla, Kalyan S.
dc.date.accessioned2005-03-21T17:44:21Z
dc.date.available2005-03-21T17:44:21Z
dc.date.issued2003
dc.identifier.urihttp://hdl.handle.net/1853/5922
dc.description.abstractBi-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.extent383335 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technologyen
dc.relation.ispartofseriesCERCS;GIT-CERCS-03-04
dc.subjectAlgorithmsen
dc.subjectBi-directional executionen
dc.subjectDestructive assignmentsen
dc.subjectLinear codesen
dc.subjectMemory resourcesen
dc.subjectOperatorsen
dc.subjectScalabilityen
dc.subjectSequence generatorsen
dc.subjectVariablesen
dc.titleGenerating Perfect Reversals of Simple Linear-Codesen
dc.typeTechnical Reporten


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record