Activities per year
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 finetune 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.
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 finetune 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.
Original language  English 

Title of host publication  Proceeedings of the 7th International Workshop on Constraint Handling Rules 
Editors  Peter Van Weert, Leslie De Koninck 
Number of pages  7 
Place of Publication  Leuven, Belgium 
Publisher  Katholieke Universiteit Leuven 
Publication date  May 2010 
Pages  1724 
Publication status  Published  May 2010 
Keywords
 Logic Programming
 Constraint Handling Rules
 Dynamic Programming
 Viterbi Algorithm
Activities
 1 Participation in workshop, seminar, course

CHR 2010: Seventh International Workshop on Constraint Handling Rules
Christian TheilHave (Participant)
20 Jul 2010Activity: Participating in or organising an event › Participation in workshop, seminar, course