From constraints to finite automata to filtering algorithms
Number of Authors: 3
2004 (English)In: Programming Languages and Systems, 13th European Symposium on Programming, ESOP 2004, Springer , 2004, 1, , 15 p.94-108 p.Conference paper (Refereed)
We introduce an approach to designing filtering algorithms by derivation from finite automata operating on constraint signatures. We illustrate this approach in two case studies of constraints on vectors of variables. This has enabled us to derive an incremental filtering algorithm that runs in O(n) plus amortized O(1) time per propagation event for the lexicographic ordering constraint over two vectors of size n, and an O(nmd) time filtering algorithm for a chain of m-1 such constraints, where d is the cost of certain domain operations. Both algorithms maintain hyperarc consistency. Our approach can be seen as a first step towards a methodology for semi-automatic development of filtering algorithms.
Place, publisher, year, edition, pages
Springer , 2004, 1. , 15 p.94-108 p.
, Lecture Notes in Computer Science, 10.1007/b96702
Computer and Information Science
IdentifiersURN: urn:nbn:se:ri:diva-22333DOI: 10.1007/b96702ISBN: 978-3-540-21313-0OAI: oai:DiVA.org:ri-22333DiVA: diva2:1041878
Proceedings ESOP2004: Programming languages and systems
Lecture Notes in Computer Science; 2986 ISBN: 978-3-540-21313-02016-10-312016-10-31