On the utility of neighbourhood singleton-style consistencies for qualitative constraint-based spatial and temporal reasoning
dc.contributor | Aalto-yliopisto | fi |
dc.contributor | Aalto University | en |
dc.contributor.author | Sioutis, Michael | en_US |
dc.contributor.author | Paparrizou, Anastasia | en_US |
dc.contributor.author | Janhunen, Tomi | en_US |
dc.contributor.department | Department of Computer Science | en |
dc.contributor.editor | Gamper, Johann | en_US |
dc.contributor.editor | Pinchinat, Sophie | en_US |
dc.contributor.editor | Sciavicco, Guido | en_US |
dc.contributor.groupauthor | Professorship Niemelä I. | en |
dc.contributor.groupauthor | Helsinki Institute for Information Technology (HIIT) | en |
dc.contributor.groupauthor | Centre of Excellence in Computational Inference, COIN | en |
dc.contributor.organization | Université d'Artois | en_US |
dc.date.accessioned | 2019-11-07T12:08:36Z | |
dc.date.available | 2019-11-07T12:08:36Z | |
dc.date.issued | 2019-10-01 | en_US |
dc.description.abstract | A 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.version | Peer reviewed | en |
dc.format.extent | 1-17 | |
dc.format.mimetype | application/pdf | en_US |
dc.identifier.citation | Sioutis, 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.14 | en |
dc.identifier.doi | 10.4230/LIPIcs.TIME.2019.14 | en_US |
dc.identifier.isbn | 9783959771276 | |
dc.identifier.issn | 1868-8969 | |
dc.identifier.other | PURE UUID: d91816ff-fcfb-4709-8d72-adecbe9955d9 | en_US |
dc.identifier.other | PURE ITEMURL: https://research.aalto.fi/en/publications/d91816ff-fcfb-4709-8d72-adecbe9955d9 | en_US |
dc.identifier.other | PURE LINK: http://www.scopus.com/inward/record.url?scp=85073546204&partnerID=8YFLogxK | en_US |
dc.identifier.other | PURE FILEURL: https://research.aalto.fi/files/38171107/LIPIcs_TIME_2019_14.pdf | en_US |
dc.identifier.uri | https://aaltodoc.aalto.fi/handle/123456789/41167 | |
dc.identifier.urn | URN:NBN:fi:aalto-201911076172 | |
dc.language.iso | en | en |
dc.publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing | |
dc.relation.ispartof | International Symposium on Temporal Representation and Reasoning | en |
dc.relation.ispartofseries | 26th International Symposium on Temporal Representation and Reasoning, TIME 2019 | en |
dc.relation.ispartofseries | Leibniz International Proceedings in Informatics, LIPIcs | en |
dc.relation.ispartofseries | Volume 147 | en |
dc.rights | openAccess | en |
dc.subject.keyword | Minimal labeling problem | en_US |
dc.subject.keyword | Neighbourhood | en_US |
dc.subject.keyword | Qualitative constraints | en_US |
dc.subject.keyword | Singleton-style consistencies | en_US |
dc.subject.keyword | Spatial and temporal reasoning | en_US |
dc.title | On the utility of neighbourhood singleton-style consistencies for qualitative constraint-based spatial and temporal reasoning | en |
dc.type | A4 Artikkeli konferenssijulkaisussa | fi |
dc.type.version | publishedVersion |