On the utility of neighbourhood singleton-style consistencies for qualitative constraint-based spatial and temporal reasoning

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorSioutis, Michaelen_US
dc.contributor.authorPaparrizou, Anastasiaen_US
dc.contributor.authorJanhunen, Tomien_US
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.editorGamper, Johannen_US
dc.contributor.editorPinchinat, Sophieen_US
dc.contributor.editorSciavicco, Guidoen_US
dc.contributor.groupauthorProfessorship Niemelä I.en
dc.contributor.groupauthorHelsinki Institute for Information Technology (HIIT)en
dc.contributor.groupauthorCentre of Excellence in Computational Inference, COINen
dc.contributor.organizationUniversité d'Artoisen_US
dc.date.accessioned2019-11-07T12:08:36Z
dc.date.available2019-11-07T12:08:36Z
dc.date.issued2019-10-01en_US
dc.description.abstractA singleton-style consistency is a local consistency that verifies if each base relation (atom) of each constraint of a qualitative constraint network (QCN) can serve as a support with respect to the closure of that network under a (naturally) weaker local consistency. This local consistency is essential for tackling fundamental reasoning problems associated with QCNs, such as the satisfiability checking or the minimal labeling problem, but can suffer from redundant constraint checks, especially when those checks occur far from where the pruning usually takes place. In this paper, we propose singleton-style consistencies that are applied just on the neighbourhood of a singleton-checked constraint instead of the whole network. We make a theoretical comparison with existing consistencies and consequently prove some properties of the new ones. In addition, we propose algorithms to enforce our consistencies, as well as parsimonious variants thereof, that are more efficient in practice than the state of the art. We make an experimental evaluation with random and structured QCNs of Interval Algebra in the phase transition region to demonstrate the potential of our approach.en
dc.description.versionPeer revieweden
dc.format.extent1-17
dc.format.mimetypeapplication/pdfen_US
dc.identifier.citationSioutis, M, Paparrizou, A & Janhunen, T 2019, On the utility of neighbourhood singleton-style consistencies for qualitative constraint-based spatial and temporal reasoning . in J Gamper, S Pinchinat & G Sciavicco (eds), 26th International Symposium on Temporal Representation and Reasoning, TIME 2019 . Leibniz International Proceedings in Informatics, LIPIcs, vol. 147, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-17, International Symposium on Temporal Representation and Reasoning, Malaga, Spain, 16/10/2019 . https://doi.org/10.4230/LIPIcs.TIME.2019.14en
dc.identifier.doi10.4230/LIPIcs.TIME.2019.14en_US
dc.identifier.isbn9783959771276
dc.identifier.issn1868-8969
dc.identifier.otherPURE UUID: d91816ff-fcfb-4709-8d72-adecbe9955d9en_US
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/d91816ff-fcfb-4709-8d72-adecbe9955d9en_US
dc.identifier.otherPURE LINK: http://www.scopus.com/inward/record.url?scp=85073546204&partnerID=8YFLogxKen_US
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/38171107/LIPIcs_TIME_2019_14.pdfen_US
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/41167
dc.identifier.urnURN:NBN:fi:aalto-201911076172
dc.language.isoenen
dc.publisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
dc.relation.ispartofInternational Symposium on Temporal Representation and Reasoningen
dc.relation.ispartofseries26th International Symposium on Temporal Representation and Reasoning, TIME 2019en
dc.relation.ispartofseriesLeibniz International Proceedings in Informatics, LIPIcsen
dc.relation.ispartofseriesVolume 147en
dc.rightsopenAccessen
dc.subject.keywordMinimal labeling problemen_US
dc.subject.keywordNeighbourhooden_US
dc.subject.keywordQualitative constraintsen_US
dc.subject.keywordSingleton-style consistenciesen_US
dc.subject.keywordSpatial and temporal reasoningen_US
dc.titleOn the utility of neighbourhood singleton-style consistencies for qualitative constraint-based spatial and temporal reasoningen
dc.typeA4 Artikkeli konferenssijulkaisussafi
dc.type.versionpublishedVersion

Files