The Viterbi Algorithm expressed in Constraint Handling Rules

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

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-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.
Original languageEnglish
Title of host publicationProceeedings of the 7th International Workshop on Constraint Handling Rules
EditorsPeter Van Weert, Leslie De Koninck
Number of pages7
Place of PublicationLeuven, Belgium
PublisherKatholieke Universiteit Leuven
Publication dateMay 2010
Pages17-24
Publication statusPublished - 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). Leuven, Belgium: Katholieke Universiteit Leuven.
Christiansen, Henning ; Have, Christian Theil ; Lassen, Ole Torp ; Petit, Matthieu. / The Viterbi Algorithm expressed in Constraint Handling Rules. Proceeedings of the 7th International Workshop on Constraint Handling Rules. editor / Peter Van Weert ; Leslie De Koninck. Leuven, Belgium : Katholieke Universiteit Leuven, 2010. pp. 17-24
@inproceedings{d104dd24799d4ec3a2f00e046a9cc8ea,
title = "The Viterbi Algorithm expressed in Constraint Handling Rules",
abstract = "The Viterbi algorithm is a classical example of a dynamic programmingalgorithm, in which pruning reduces the search space drastically,so that an otherwise exponential time complexity is reduced to linearity. Thecentral steps of the algorithm, expansion and pruning, can be expressed ina concise and clear way in CHR, but additional control is needed in orderto obtain the desired time complexity. It is shown how auxiliary constraints,called trigger constraints, can be applied to fine-tune the order of CHR ruleapplications in order to reach this goal. It is indicated how properties suchas confluence can be useful for showing such optimized programs correct.",
keywords = "Logic Programming, Constraint Handling Rules, Dynamic Programming, Viterbi Algorithm",
author = "Henning Christiansen and Have, {Christian Theil} and Lassen, {Ole Torp} and Matthieu Petit",
year = "2010",
month = "5",
language = "English",
pages = "17--24",
editor = "{Van Weert}, Peter and {De Koninck}, Leslie",
booktitle = "Proceeedings of the 7th International Workshop on Constraint Handling Rules",
publisher = "Katholieke Universiteit Leuven",

}

Christiansen, H, Have, CT, Lassen, OT & 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. Katholieke Universiteit Leuven, Leuven, Belgium, pp. 17-24.

The Viterbi Algorithm expressed in Constraint Handling Rules. / Christiansen, Henning; Have, Christian Theil; Lassen, Ole Torp; Petit, Matthieu.

Proceeedings of the 7th International Workshop on Constraint Handling Rules. ed. / Peter Van Weert; Leslie De Koninck. Leuven, Belgium : Katholieke Universiteit Leuven, 2010. p. 17-24.

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

TY - GEN

T1 - The Viterbi Algorithm expressed in Constraint Handling Rules

AU - Christiansen, Henning

AU - Have, Christian Theil

AU - Lassen, Ole Torp

AU - Petit, Matthieu

PY - 2010/5

Y1 - 2010/5

N2 - The Viterbi algorithm is a classical example of a dynamic programmingalgorithm, in which pruning reduces the search space drastically,so that an otherwise exponential time complexity is reduced to linearity. Thecentral steps of the algorithm, expansion and pruning, can be expressed ina concise and clear way in CHR, but additional control is needed in orderto obtain the desired time complexity. It is shown how auxiliary constraints,called trigger constraints, can be applied to fine-tune the order of CHR ruleapplications in order to reach this goal. It is indicated how properties suchas confluence can be useful for showing such optimized programs correct.

AB - The Viterbi algorithm is a classical example of a dynamic programmingalgorithm, in which pruning reduces the search space drastically,so that an otherwise exponential time complexity is reduced to linearity. Thecentral steps of the algorithm, expansion and pruning, can be expressed ina concise and clear way in CHR, but additional control is needed in orderto obtain the desired time complexity. It is shown how auxiliary constraints,called trigger constraints, can be applied to fine-tune the order of CHR ruleapplications in order to reach this goal. It is indicated how properties suchas confluence can be useful for showing such optimized programs correct.

KW - Logic Programming

KW - Constraint Handling Rules

KW - Dynamic Programming

KW - Viterbi Algorithm

M3 - Article in proceedings

SP - 17

EP - 24

BT - Proceeedings of the 7th International Workshop on Constraint Handling Rules

A2 - Van Weert, Peter

A2 - De Koninck, Leslie

PB - Katholieke Universiteit Leuven

CY - Leuven, Belgium

ER -

Christiansen H, Have CT, Lassen OT, Petit M. The Viterbi Algorithm expressed in Constraint Handling Rules. In Van Weert P, De Koninck L, editors, Proceeedings of the 7th International Workshop on Constraint Handling Rules. Leuven, Belgium: Katholieke Universiteit Leuven. 2010. p. 17-24