Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
From constraints to finite automata to filtering algorithms
RISE., Swedish ICT, SICS, Computer Systems Laboratory.ORCID-id: 0000-0003-3079-8095
2004 (Engelska)Ingår i: Proceedings ESOP2004: Programming languages and systems, Springer , 2004, 1, , s. 15s. 94-108Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
Springer , 2004, 1. , s. 15s. 94-108
Serie
Lecture Notes in Computer Science ; 2986
Nationell ämneskategori
Data- och informationsvetenskap
Identifikatorer
URN: urn:nbn:se:ri:diva-22333DOI: 10.1007/b96702ISBN: 978-3-540-21313-0 (tryckt)OAI: oai:DiVA.org:ri-22333DiVA, id: diva2:1041878
Konferens
Programming Languages and Systems, 13th European Symposium on Programming, ESOP 2004, 29 March - 2 April 2004, Barcelona, Spain
Anmärkning

Lecture Notes in Computer Science; 2986 ISBN: 978-3-540-21313-0

Tillgänglig från: 2016-10-31 Skapad: 2016-10-31 Senast uppdaterad: 2025-09-23Bibliografiskt granskad

Open Access i DiVA

fulltext(160 kB)224 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 160 kBChecksumma SHA-512
d4956ba95b1c35783a66598a50b5e048c2a8384edfff37bbacfa7c9320abe51d982525947ffcb3bf59c43b11b6c8ddff4f5517625fbfb07b81124b430d771a19
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltext

Person

Carlsson, Mats

Sök vidare i DiVA

Av författaren/redaktören
Carlsson, Mats
Av organisationen
Computer Systems Laboratory
Data- och informationsvetenskap

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 224 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 195 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf