The Viterbi Algorithm expressed in Constraint Handling Rules

Henning Christiansen, Christian Theil Have, Ole Torp Lassen, Matthieu Petit

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review

Abstract

The Viterbi algorithm is a classical example of a dynamic programming
algorithm, in which pruning reduces the search space drastically,
so that an otherwise exponential time complexity is reduced to linearity. The
central steps of the algorithm, expansion and pruning, can be expressed in
a concise and clear way in CHR, but additional control is needed in order
to obtain the desired time complexity. It is shown how auxiliary constraints,
called trigger constraints, can be applied to fine-tune the order of CHR rule
applications in order to reach this goal. It is indicated how properties such
as confluence can be useful for showing such optimized programs correct.
OriginalsprogEngelsk
TitelProceeedings of the 7th International Workshop on Constraint Handling Rules
RedaktørerPeter Van Weert, Leslie De Koninck
Antal sider7
Udgivelses stedLeuven, Belgium
ForlagKatholieke Universiteit Leuven
Publikationsdatomaj 2010
Sider17-24
StatusUdgivet - maj 2010

Citer dette