Change search
ReferencesLink to record
Permanent link

Direct link
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)
Abstract [en]

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
National Category
Computer and Information Science
URN: urn:nbn:se:ri:diva-22333DOI: 10.1007/b96702ISBN: 978-3-540-21313-0OAI: diva2:1041878
Proceedings ESOP2004: Programming languages and systems
Lecture Notes in Computer Science; 2986 ISBN: 978-3-540-21313-0Available from: 2016-10-31 Created: 2016-10-31

Open Access in DiVA

fulltext(160 kB)2 downloads
File information
File name FULLTEXT01.pdfFile size 160 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 2 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 2 hits
ReferencesLink to record
Permanent link

Direct link