Learning Centre

Collective singleton-based consistency for qualitative constraint networks: Theory and practice

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Sioutis, Michael
dc.contributor.author Paparrizou, Anastasia
dc.contributor.author Condotta, Jean-François
dc.date.accessioned 2020-01-02T13:57:03Z
dc.date.available 2020-01-02T13:57:03Z
dc.date.issued 2019-01-01
dc.identifier.citation Sioutis , M , Paparrizou , A & Condotta , J-F 2019 , ' Collective singleton-based consistency for qualitative constraint networks: Theory and practice ' , Theoretical Computer Science , vol. 797 , pp. 17-41 . https://doi.org/10.1016/j.tcs.2019.02.028 en
dc.identifier.issn 0304-3975
dc.identifier.other PURE UUID: 420e4ecc-2110-4b46-b719-a57b177f26c8
dc.identifier.other PURE ITEMURL: https://research.aalto.fi/en/publications/collective-singletonbased-consistency-for-qualitative-constraint-networks-theory-and-practice(420e4ecc-2110-4b46-b719-a57b177f26c8).html
dc.identifier.other PURE LINK: http://www.scopus.com/inward/record.url?scp=85063109256&partnerID=8YFLogxK
dc.identifier.other PURE FILEURL: https://research.aalto.fi/files/32571944/SCI_Sioutis_et.al._Collective_Singleton_based_SPC_TCS_2019.pdf
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/41998
dc.description Avaa tiedosto embargolla sitten kun julkaisu ilmestyy.
dc.description.abstract Partial singleton weak path-consistency, or partial (Figure presented.)-consistency for short, is essential for tackling challenging fundamental reasoning problems associated with qualitative constraints networks. Briefly put, partial (Figure presented.)-consistency ensures that each base relation of each of the constraints of a qualitative constraint network can define a singleton relation in its corresponding partially weakly path-consistent, or partially ⋄-consistent for short, subnetwork. In this paper, we propose a stronger local consistency that couples (Figure presented.)-consistency with the idea of collectively deleting certain unfeasible base relations by exploiting singleton checks. We then propose an algorithm for enforcing this new consistency and a lazy variant of that algorithm for approximating the new consistency that, given a qualitative constraint network, both outperform the respective algorithm for enforcing partial (Figure presented.)-consistency in that network. With respect to the lazyalgorithmic variant in particular, we show that it runs up to 5 times faster than our original exhaustive algorithm whilst exhibiting very similar pruning capability. We formally prove certain properties of our new local consistency and our algorithms, and motivate their usefulness through demonstrative examples and a thorough experimental evaluation with random qualitative constraint networks of the Interval Algebra and the Region Connection Calculus from the phase transition region of two different generation models. Finally, we provide evidence of the crucial role of the new consistency in tackling the minimal labeling problem of a qualitative constraint network, which is the problem of finding the strongest implied constraints of that network. en
dc.format.mimetype application/pdf
dc.language.iso en en
dc.publisher ELSEVIER SCIENCE BV
dc.relation.ispartofseries Theoretical Computer Science en
dc.rights openAccess en
dc.subject.other Theoretical Computer Science en
dc.subject.other Computer Science(all) en
dc.subject.other 113 Computer and information sciences en
dc.title Collective singleton-based consistency for qualitative constraint networks: Theory and practice en
dc.type A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä fi
dc.description.version Peer reviewed en
dc.contributor.department Department of Computer Science
dc.contributor.department Centre de Recherche en Informatique de Lens
dc.subject.keyword Qualitative constraint network
dc.subject.keyword Singleton style consistency
dc.subject.keyword Spatial and temporal reasoning
dc.subject.keyword Theoretical Computer Science
dc.subject.keyword Computer Science(all)
dc.subject.keyword 113 Computer and information sciences
dc.identifier.urn URN:NBN:fi:aalto-202001021109
dc.identifier.doi 10.1016/j.tcs.2019.02.028
dc.date.embargo info:eu-repo/date/embargoEnd/2020-12-31


Files in this item

Files Size Format View

There are no open access files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse