Christiansen, Henning1; Have, Christian Theil1; Lassen, Ole Torp1; Petit, Matthieu1
Peter Van Weert, Leslie De Koninck
1 Programming, Logic and Intelligent Systems, Department of People and Technology, Roskilde University2 The Department of Communication, Business and Information Technologies, Roskilde University
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.
Proceeedings of the 7th International Workshop on Constraint Handling Rules, 2010, p. 17-24