Implementation of Logical Retraction in Constraint Handling Rules with Justifications

Autor:	Thom Frühwirth
Rok vydání:	2018
Předmět:	Constraint Handling Rules Mathematical optimization Transformation (function) Work (electrical) Dynamic problem Conservative extension Computer science Benchmark (computing) Time complexity
Zdroj:	Declarative Programming and Knowledge Management ISBN: 9783030008000 DECLARE
DOI:	10.1007/978-3-030-00801-7_3
Popis:	In previous work we added justifications to Constraint Handling Rules (CHR) to enable logical retraction of constraints for dynamic algorithms. We presented a straightforward source-to-source transformation to implement this conservative extension. In this companion paper, we improve the performance of the transformation. We discuss its worst-case time complexity in general. Then we perform experiments. We benchmark the dynamic problem of maintaining shortest paths under addition and retraction of paths. The results validate our complexity considerations.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::cfc3224121a8cafe3800b423e527dce6 https://doi.org/10.1007/978-3-030-00801-7_3 Zobrazit plný text záznamu