aalto1 untyped-item.component.html
Collective singleton-based consistency for qualitative constraint networks: Theory and practice
Loading...
Access rights
openAccess
acceptedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
Theoretical Computer Science, Volume 797, pp. 17-41
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 lazy algorithmic 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.
Description
Avaa tiedosto embargolla sitten kun julkaisu ilmestyy.
Other note
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