6533b7d3fe1ef96bd1261566

RESEARCH PRODUCT

Transducers for the bidirectional decoding of prefix codes

Sabrina MantaciLaura Giambruno

subject

Prefix codeGeneral Computer ScienceSettore INF/01 - InformaticaGeneralizationComputer scienceGirod’s encodingTransducersPrefix codeTheoretical Computer SciencePrefixTransducerPrefix codesAlgorithmDecoding methodsWord (computer architecture)Computer Science(all)

description

AbstractWe construct a transducer for the bidirectional decoding of words encoded by the method introduced by Girod (1999) in [5] and we prove that it is bideterministic and that it can be used both for the left-to-right and the right-to-left decoding.We also give a similar construction for a transducer that decodes in both directions words encoded by a generalization of Girod’s encoding method. We prove that it has the same properties as those of the previous transducer. In addition we show that it has a single initial/final state and that it is minimal.

yearjournalcountryeditionlanguage
2010-03-01
10.1016/j.tcs.2010.01.033http://hdl.handle.net/10447/46213