### 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.

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.

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 | 17-24 |

Publication status | Published - May 2010 |

### Keywords

- Logic Programming
- Constraint Handling Rules
- Dynamic Programming
- Viterbi Algorithm

## Cite this

Christiansen, H., Have, C. T., Lassen, O. T., & Petit, M. (2010). The Viterbi Algorithm expressed in Constraint Handling Rules. In P. Van Weert, & L. De Koninck (Eds.),

*Proceeedings of the 7th International Workshop on Constraint Handling Rules*(pp. 17-24). Katholieke Universiteit Leuven. http://www.cs.kuleuven.be/publicaties/rapporten/cw/CW588.pdf