Michael Sioutis
email: michail.sioutis@uni-bamberg.de

Anastasia Paparrizou
email: paparrizou@cril.fr

Tomi Janhunen
email: tomi.janhunen@tuni.fi

On Neighbourhood Singleton-style Consistencies for Qualitative Spatial and Temporal Reasoning

Keywords: Qualitative constraints, spatial and temporal reasoning, singleton-style consistencies, neighbourhood, minimal labeling problem

Given a qualitative constraint network (QCN), a singleton-style consistency is a local consistency that focuses on each base relation (atom) of a constraint separately, rather than the entire constraint altogether. More technically, such a consistency verifies if each base relation of each constraint of a QCN can serve as a support with respect to the closure of that network under a (naturally) weaker local consistency. This 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 Allen's Interval Algebra in the phase transition region to demonstrate the potential of our approach.

Introduction

Qualitative Spatial and Temporal Reasoning (QSTR) is a Symbolic AI approach that deals with the fundamental cognitive concepts of space and time in a qualitative, human-like, manner [START_REF] Ligozat | Qualitative Spatial and Temporal Reasoning[END_REF][START_REF] Dylla | A Survey of Qualitative Spatial and Temporal Calculi: Algebraic and Computational Properties[END_REF]. For instance, in natural language one uses expressions such as inside, before, and north of to spatially or temporally relate one object with another object or oneself, without resorting to providing quantitative information about these entities. More formally, QSTR restricts the vocabulary of rich mathematical theories that deal with spatial and temporal entities to simple qualitative constraint languages. Thus, QSTR provides a concise framework that allows for rather inexpensive reasoning about entities located in space and time and, hence, further boosts research and applications to a plethora of areas and domains that include, but are not limited to, dynamic GIS [START_REF] Bhatt | Geospatial Narratives and Their Spatio-Temporal Dynamics: Commonsense Reasoning for High-Level Analyses in Geographic Information Systems[END_REF], cognitive robotics [START_REF] Dylla | Qualitative Spatial Reasoning with Conceptual Neighborhoods for Agent Control[END_REF], deep learning [START_REF] Krishnaswamy | Combining Deep Learning and Qualitative Spatial Reasoning to Learn Complex Structures from Sparse Examples with Noise[END_REF], spatio-temporal design [START_REF] Story | A Design Support Environment for Spatio-Temporal Database Applications[END_REF], qualitative model generation from video [START_REF] Dubba | Learning Relational Event Models from Video[END_REF], ambient intelligence [START_REF] Bhatt | Spatio-terminological Inference for the Design of Ambient Environments[END_REF][START_REF] Sioutis | Towards a Synergy of Qualitative Spatio-Temporal Reasoning and Smart Environments for Assisting the Elderly at Home[END_REF], visual explanation [START_REF] Suchan | Visual Explanation by High-Level Abduction: On Answer-Set Programming Driven Reasoning About Moving Objects[END_REF] and sensemaking [START_REF] Suchan | Out of Sight But Not Out of Mind: An Answer Set Programming Based Online Abduction Framework for Visual Sensemaking in Autonomous Driving[END_REF], semantic question-answering [START_REF] Suchan | Semantic Question-Answering with Video and Eye-Tracking Data: AI Foundations for Human Visual Perception Driven Cognitive Film Studies[END_REF], qualitative simulation [START_REF] Cui | Qualitative Simulation Based on a Logical Formalism of Space and Time[END_REF], spatio-temporal data mining [START_REF] Moskovitch | Classification of multivariate time series via temporal abstraction and time intervals mining[END_REF][START_REF] Kostakis | On searching and indexing sequences of temporal intervals[END_REF][START_REF] Kostakis | Discovering recurring activity in temporal networks[END_REF], and modal logic [START_REF] Morales | A new modal logic for reasoning about space: spatial propositional neighborhood logic[END_REF][START_REF] Muñoz-Velasco | On coarser interval temporal logics[END_REF][START_REF] Bresolin | Decidability and complexity of the fragments of the modal logic of Allen's relations over the rationals[END_REF]. The interested reader may look into a more comprehensive review of the emerging applications, the trends, and the future directions of QSTR in [START_REF] Hazarika | Qualitative Spatio-Temporal Representation and Reasoning: Trends and Future Directions[END_REF][START_REF] Bhatt | Qualitative Spatial and Temporal Reasoning: Emerging Applications[END_REF]. In addition, a detailed survey of qualitative spatial and temporal calculi appears in [START_REF] Dylla | A Survey of Qualitative Spatial and Temporal Calculi: Algebraic and Computational Properties[END_REF].

Qualitative spatial or temporal information can be modeled as a qualitative constraint network (QCN), which is defined as a network where the vertices correspond to spatial or temporal entities, and the arcs are labelled with qualitative spatial or temporal relations respectively. For instance x ≤ y can be a temporal QCN over Z. Two fundamental reasoning problems associated with a given QCN N are the problems of satisfiability checking and minimal labeling (or deductive closure) [START_REF] Renz | Qualitative Spatial Reasoning Using Constraint Calculi[END_REF]. In particular, the satisfiability checking problem is about deciding if there exists a valuation of the variables of N that satisfies its constraints, such a valuation being called a solution of N , and the minimal labeling problem concerns finding the strongest implied constraints and consequently obtaining its minimal sub-network. For instance, x = 0 ∧ y = 1 is one of the (infinitely many) solutions of the aforementioned QCN, and x ≤ y is already the strongest implied constraint as it is possible to have both solutions that satisfy x < y, e.g., x = 0 ∧ y = 1, and solutions that satisfy x = y, e.g., x = 0 ∧ y = 0; so, in fact, the QCN is minimal. In general, for many well known spatio-temporal calculi the satisfiability checking problem is NP-hard [START_REF] Dylla | Algebraic Properties of Qualitative Spatio-Temporal Calculi[END_REF]. Further, the minimal labeling problem is polynomial-time Turing reducible to the satisfiability checking problem [START_REF] Golumbic | Complexity and Algorithms for Reasoning about Time: A Graph-Theoretic Approach[END_REF].

Motivation

In this paper, we focus mostly on the minimal labeling problem, which, since its introduction in 1974 by Montanari [START_REF] Montanari | Networks of constraints: Fundamental properties and applications to picture processing[END_REF], has been studied in the domains of both CSPs [START_REF] Gottlob | On minimal constraint networks[END_REF][START_REF] Van Beek | On the Minimality and Decomposability of Row-Convex Constraint Networks[END_REF] and QCNs [START_REF] Gerevini | Computing the minimal relations in point-based qualitative temporal reasoning through metagraph closure[END_REF][START_REF] Liu | Solving Minimal Constraint Networks in Qualitative Spatial and Temporal Reasoning[END_REF]. A trivial example of how minimality applies to QCNs was presented earlier, and a more detailed one follows. As noted in [START_REF] Gottlob | On minimal constraint networks[END_REF], a minimal network is a quite useful knowledge compilation, since it allows one to answer a number of queries in polynomial time that would otherwise be NP-hard. Indeed, in the context of QSTR, for instance, one could exploit minimality of a QCN to immediately deduce whether a task A should be scheduled before a task C, or whether an object X could be placed on top of an object Z. A visualization of the former example is provided in Figure 1; the initial QCN is not minimal, but becomes such by removing the base relation after from the constraint involving Tasks A and C, as that base relation is impossible to be satisfied by any solution. Difficult problems such as the minimal labeling problem and alike are, in general, either approximated by the use of local consistencies [START_REF] Van Beek | On the Minimality and Decomposability of Row-Convex Constraint Networks[END_REF] or even solved by the aid of such consistencies [START_REF] Amaneddine | Efficient Approach to Solve the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints[END_REF]. In fact, in time-critical applications approximation may be the sole possibility, as solving the problem often takes significantly more time (it is NP-hard after all) and may only guarantee a marginally better result (if at all) in terms of minimal labeling (see the performance of Minimizer in Tables 1 and2). Among the local consistencies introduced in the literature, we study singleton-style consistencies in the aforementioned context, which are consistencies that entail support for each base relation (atom) of the constraints of a QCN with respect to the closure of that network under a weaker local consistency (typically G -consistency [START_REF] Chmeiss | Consistency of Triangulated Temporal Qualitative Constraint Networks[END_REF][START_REF] Renz | Weak Composition for Qualitative Spatial and Temporal Reasoning[END_REF]). Specifically, we investigate how these consistencies behave when the underlying weaker local consistency that they build upon is restricted to the neighbourhood of a singleton-checked constraint. As noted in [START_REF] Wallace | Neighbourhood SAC: Extensions and new algorithms[END_REF], neighbourhood-based restrictions can hit the sweet spot between effectiveness and efficiency in singleton-style consistencies for CSPs; therefore, it is imperative that we introduce and study such restrictions in the context of QCNs as well, and consequently provide a foundation for further work in understanding these kinds of network structures, which have received much attention over the past years [START_REF] Dylla | A Survey of Qualitative Spatial and Temporal Calculi: Algebraic and Computational Properties[END_REF].

Contributions

Our contributions are fivefold and described as follows:

i) we enrich the family of consistencies for QCNs by proposing singleton-style consistencies that are applied just on the neighbourhood of the singletonchecked constraint instead of the entire network;

ii) we theoretically obtain a strength-based hierarchy among existing consistencies for QCNs and the novel ones;

iii) we present algorithms to enforce the proposed consistencies for QCNs, as well as parsimonious variants thereof; iv) we make an experimental evaluation with random and structured QCNs of Interval Algebra to measure and compare the performance of all considered algorithms, especially in terms of how fast and how well they can independently approximate the minimal sub-network of a QCN; v) we review the latest related work that exists in the area of traditional constraint programming, discuss similarities and differences with respect to our approach, and give some directions for future work.

Organization

The rest of the paper is organized as follows. In Section 2 we give some preliminaries on qualitative spatial and temporal reasoning. Next, in Section 3 we overview some known state-of-the-art local consistencies for QCNs. Then, in Section 4 we introduce, formally define, and thoroughly study the proposed neighbourhood-based consistencies for QCNs, and present the algorithms for enforcing these consistencies, as well as parsimonious variants thereof. In Section 5 we evaluate our approach with random and structured QCNs of Interval Algebra and comment on the outcome; one finding is that neighbourhood-focused singleton-style algorithms are around 30% faster in the phase transition region than the standard algorithms, and another one is that they exhibit an improved efficiency to effectiveness ratio of up to around 25%. Next, in Section 6 we review the latest related work that exists in the discussed direction. Finally, in Section 7 we draw some conclusive remarks and give directions for future work.

Preliminaries

A binary qualitative spatial or temporal constraint language, is based on a finite set B of jointly exhaustive and pairwise disjoint relations, called the set of base relations [START_REF] Ligozat | What Is a Qualitative Calculus? A General Framework[END_REF], that is defined over an infinite domain D. The base relations of a particular qualitative constraint language can be used to represent the definite knowledge between any two of its entities with respect to the level of granularity provided by the domain D. The set B contains the identity relation Id, and is closed under the converse operation ( -1 ). Indefinite knowledge can be specified by a union of possible base relations, and is represented by the set containing them. Hence, 2 B represents the total set of relations. The set 2 B is equipped with the usual set-theoretic operations of union and intersection, the converse operation, and the weak composition operation denoted by the symbol [START_REF] Ligozat | What Is a Qualitative Calculus? A General Framework[END_REF]. For all r ∈ 2 B , we have that r As an illustration, consider the well known qualitative temporal constraint language of Interval Algebra (IA), introduced by Allen [START_REF] Allen | Maintaining Knowledge about Temporal Intervals[END_REF]. Its domain is defined to be the set of intervals on Q, i.e., Then, IA considers such time intervals as its temporal entities, and the set of base relations B = {eq, p, pi, m, mi, o, oi, s, si, d, di, f , f i} as a means to encode knowledge about the temporal relations between the entities, as depicted in Figure 2. Specifically, each base relation represents a particular ordering of the four endpoints of two intervals on the timeline. For example, d, viz., during, is defined as d = {(x, y) ∈ D × D | x -> y -and x + < y + }. Of those base relations, eq is the identity relation Id, for which it holds that eq -1 = eq. Typical applications of Interval Algebra involve-in addition to those listed for QSTR in the introduction-planning and scheduling [START_REF] Allen | Planning Using a Temporal World Model[END_REF][START_REF] Allen | Planning as Temporal Reasoning[END_REF][START_REF] Pelavin | A Model for Concurrent Actions Having Temporal Extent[END_REF][START_REF] Dorn | Dependable Reactive Event-Oriented Planning[END_REF][START_REF] Mudrová | Task scheduling for mobile robots using interval algebra[END_REF], natural language processing [START_REF] Song | The Interpretation of Temporal Relations in Narrative[END_REF][START_REF] Denis | Predicting Globally-Coherent Temporal Structures from Texts via Endpoint Inference and Graph Decomposition[END_REF], temporal databases [START_REF] Snodgrass | The Temporal Query Language TQuel[END_REF][START_REF] Chen | Universal Temporal Data Languages[END_REF], multimedia databases [START_REF] Little | Interval-Based Conceptual Models for Time-Dependent Multimedia Data[END_REF], molecular biology [START_REF] Golumbic | Complexity and Algorithms for Reasoning about Time: A Graph-Theoretic Approach[END_REF] (e.g., arrangement of DNA segments/intervals along a linear chain involves particular temporal-like problems [START_REF] Benzer | On the Topology of the Genetic Fine Structure[END_REF]), workflow [START_REF] Lu | Using a temporal constraint network for business process execution[END_REF], and temporal diagnosis [START_REF] Gamper | Abstract temporal diagnosis in medical domains[END_REF].

D = {x = (x -, x + ) ∈ Q × Q : x -< x + }.
Notably, many (if not most) of the well known and well studied qualitative constraint languages, such as Interval Algebra [START_REF] Allen | Maintaining Knowledge about Temporal Intervals[END_REF] and RCC8 [START_REF] Randell | A Spatial Logic Based on Regions & Connection[END_REF], are in fact relation algebras [START_REF] Dylla | Algebraic Properties of Qualitative Spatio-Temporal Calculi[END_REF]. In what follows, we restrict ourselves to such calculi in order to facilitate discussion of the consistencies and of the algorithms for enforcing them.

Qualitative spatial or temporal information can be modeled as a qualitative constraint network, defined in the following manner: • V = {v 1 , . . . , v n } is a non-empty finite set of variables;

x 1 x 2 x 3 x 4 {p, m} B {d, s, si} {oi} {oi, m} {pi, eq} (a) A satisfiable QCN N x 1 x 2 x 3 x 4 (b) A solution σ of N
• and C is a mapping

C : V × V → 2 B such that C(v, v) = {Id} for all v ∈ V and C(v, v ) = (C(v , v)) -1 for all v, v ∈ V .
An example of a QCN of IA is shown in Figure 3a; for clarity, converse relations as well as Id loops are not mentioned nor shown in the figure .   Definition 2. Let N = (V, C) be a QCN, then: 3b);

• a solution of N is a mapping σ : V → D such that ∀(u, v) ∈ V × V , ∃b ∈ C(u, v) such that (σ(u), σ(v)) ∈ b (see Figure
• N is satisfiable if and only if it admits a solution;

• a sub-QCN N of N , denoted by N ⊆ N , is a QCN (V, C ) such that C (u, v) ⊆ C(u, v) ∀u, v ∈ V ; if in addition ∃u, v ∈ V such that C (u, v) ⊂ C(u, v), then N ⊂ N ; • a base relation b ∈ C(v, v ) with v, v ∈ V is feasible (resp. unfeasible)
in N if and only if there exists (resp. there does not exist) a solution σ :

V → D of N such that (σ(v), σ(v )) ∈ b; • N is minimal if and only if ∀v, v ∈ V and ∀b ∈ C(v, v ), b is a feasible base relation in N ;
• the constraint graph of N , denoted by G(N ), is the graph (V, E) where

{u, v} ∈ E if and only if C(u, v) = B and u = v; • N is the empty QCN on V , denoted by ⊥ V , if and only if C(u, v) = ∅ for all u, v ∈ V with u = v.
Let us further introduce the following operation that substitutes C(v, v ) with r ∈ 2 B in a given QCN:

• given a QCN N = (V, C) and v, v ∈ V , we define that N [v,v ]/r with r ∈ 2 B yields the QCN N = (V, C ) defined by C (v, v ) = r, C (v , v) = r -1 , and ∀(u, u ) ∈ (V × V ) \ {(v, v ), (v , v)}, C (u, u ) = C(u, u ).

State-of-the-art Consistencies

We view a consistency φ G , where φ is some operation (such as the weak composition operation) and G a graph, as a predicate on QCNs, i.e., a function that receives an input QCN and returns true or false depending on whether φ G holds on that QCN or not respectively. In what follows, given some operation φ (such as the weak composition operation) and a graph G, the unique ⊆-maximal

φ G -consistent sub-QCN of N is called the closure of N under the consistency φ G
and is denoted by φ G (N ). We recall the definition of G -consistency, which is a basic and widely used local consistency for reasoning with QCNs.

Definition 3. Given a QCN N = (V, C) and a graph G = (V , E), where V ⊆ V , N is said to be G -consistent if and only if ∀{v i , v j }, {v i , v k }, {v k , v j } ∈ E we have that C(v i , v j ) ⊆ C(v i , v k ) C(v k , v j ).
Intuitively, G -consistency entails consistency for all triples of variables of a QCN that correspond to triangles of a given graph G. If G is the complete graph on the variables of a given QCN, then G -consistency becomes identical to -consistency [START_REF] Renz | Weak Composition for Qualitative Spatial and Temporal Reasoning[END_REF], and, hence, -consistency can be seen as a special case of G -consistency.

In [START_REF] Sioutis | Efficiently Reasoning about Qualitative Constraints through Variable Elimination[END_REF] the authors build upon G -consistency and propose a local consistency in the context of qualitative constraint-based reasoning that serves as the counterpart of directional path consistency in traditional constraint programming [START_REF] Dechter | Network-Based Heuristics for Constraint-Satisfaction Problems[END_REF] or quantitative temporal reasoning [START_REF] Dechter | Temporal Constraint Networks[END_REF], and is mainly distinguished by the fact that the involved consistency notions are tailored to handle infinite domains and qualitative relations. This local consistency is called ← -G -consistency and, in particular, it entails consistency for all ordered triples of variables of a QCN that correspond to triangles of a given graph G; this ordering can be specified by a bijection between the set of the variables of a QCN and a set of integers, and can be chosen randomly or via an algorithm or heuristic. We recall the formal definition of that consistency as follows:

Definition 4. Given a QCN N = (V, C), an ordering (α -1 (0),α -1 (1),. . ., α -1 (n-1)) of V defined by a bijection α : V → {0, 1, . . . , n-1}, and a graph G = (V , E), where V ⊆ V , N is said to be ← - G -consistent if and only if ∀v i , v j , v k ∈ V such that {v i , v j }, {v i , v k }, {v k , v j } ∈ E and α(v i ), α(v j ) < α(v k ) we have that C(v i , v j ) ⊆ C(v i , v k ) C(v k , v j ). Since ← -
G -consistency is basically G -consistency restricted to some ordering of the triples of variables of a given QCN, it is expected that it will perform worse than G -consistency in terms of tackling the satisfiability checking or the minimal labeling problem of that QCN, in the general case. However, that behaviour of ← -G -consistency in the context of the aforementioned reasoning problems for arbitrary QCNs has yet to be investigated (cf. [START_REF] Sioutis | Leveraging Variable Elimination for Efficiently Reasoning about Qualitative Constraints[END_REF]), and we shall use this work as an opportunity to do so (see Section 5).

We continue with the presentation of some state-of-the-art singleton-style

consistencies. Given a graph G = (V , E), where V ⊆ V , a QCN N = (V, C) is ◆ G -consistent if
and only if for every pair of variables {v, v } ∈ E and every base relation b ∈ C(v, v ), after instantiating C(v, v ) with {b} as the singleton and applying G -consistency on N , the revised constraint C(v, v ) is always supported by {b}. Formally, ◆ G -consistency of a QCN is defined as follows:

Definition 5. Given a QCN N = (V, C) and a graph G = (V , E), where V ⊆ V , N is said to be ◆ G -consistent if and only if N is G -consistent and ∀{v, v } ∈ E and ∀b ∈ C(v, v ) we have that C (v, v ) = {b}, where (V, C ) = G (N [v,v ]/{b} ).
If G is the complete graph on the variables of a given QCN, we can easily verify that ◆ G -consistency corresponds to B -consistency of the family of fconsistencies studied in [START_REF] Condotta | A Class of f -Consistencies for Qualitative Constraint Networks[END_REF]. Interestingly, ◆ G -consistency for QCNs can also be seen as a counterpart of Singleton Arc Consistency (SAC) [START_REF] Debruyne | Some Practicable Filtering Techniques for the Constraint Satisfaction Problem[END_REF] for CSPs.

Finally, in [START_REF] Sioutis | Collective Singleton-Based Consistency for Qualitative Constraint Networks[END_REF] the authors define a local consistency that is more restrictive than any of the practical1 local consistencies known to date for QCNs, called collective ◆ G -consistency, or ◆ ∪ G -consistency for short. This singleton-style consistency is inspired by k-partitioning consistency for CSPs [START_REF] Bennaceur | Partition-k-AC: An Efficient Filtering Technique Combining Domain Partition and Arc Consistency[END_REF]. We recall the formal definition of that consistency as follows:

Definition 6. Given a QCN N = (V, C) and a graph G = (V , E), where V ⊆ V , N is said to be ◆ ∪ G -consistent if and only if N is ◆ G -consistent and ∀{v, v } ∈ E, ∀b ∈ C(v, v ), and ∀{u, u } ∈ E we have that ∃b ∈ C(u, u ) such that b ∈ C (v, v ), where (V, C ) = G (N [u,u ]/{b } ).

This underlying filtering condition of ◆ ∪

G -consistency is based on relation partitioning combined with G -consistency, and allows for improved pruning capability over ◆ G -consistency [START_REF] Sioutis | Collective Singleton-Based Consistency for Qualitative Constraint Networks[END_REF].

Neighbourhood Singleton-style Consistencies

In this section we propose and study a variety of singleton-style consistencies that are applied just on the neighbourhood of the singleton-checked constraint instead of the whole network.

Before doing so, let us first formally introduce a preorder in order to compare the pruning ( G , and vice versa. In general, standard singleton-style consistencies can make a lot of redundant checks, which consequently can slow down their efficacy. It has been observed in the domain of CSPs that the majority of constraint revisions occur close to the relation that is being singleton checked, and rarely too far from it [START_REF] Wallace | Neighbourhood SAC: Extensions and new algorithms[END_REF]. For that purpose, constraint programming researchers have proposed weaker singleton-style consistencies that localize propagation to the neighbourhood of the variable at hand [START_REF] Wallace | Neighbourhood SAC: Extensions and new algorithms[END_REF][START_REF] Paparrizou | On Neighborhood Singleton Consistencies[END_REF]. Neighbourhood singleton-style consistencies for CSPs, despite being strictly weaker than SAC [START_REF] Debruyne | Some Practicable Filtering Techniques for the Constraint Satisfaction Problem[END_REF] in general, can produce almost as much filtering as SAC with substantially less computational cost on many problems [START_REF] Paparrizou | On Neighborhood Singleton Consistencies[END_REF]. In what follows, we define two neighbourhood singletonstyle consistencies for QCNs, and then we proceed to present algorithms and parsimonious variants thereof for applying these consistencies efficiently.

In order to define the new consistencies, we first need to define what exactly is meant by "neighbourhood of a relation" in the context of QCNs. Informally, given a QCN N and a graph G, the neighbourhood of a relation in N comprises all the triangles that involve the corresponding edge in G, and all the edges among the vertices of those triangles as well. Noting that in a given graph G = (V, E), for each u ∈ V the set of adjacent vertices of u, denoted by adj(u), is the set {w | {u, w} ∈ E}, we can formally define the neighbourhood of a relation of a QCN as follows:

Definition 7. Given a QCN N = (V, C), a graph G = (V , E), where V ⊆ V , and two variables v, v ∈ V such that {v, v } ∈ E, the neighbourhood of C(v, v ), denoted by G N(vv ) , is the induced subgraph G[S], where S = (adj(v) ∩ adj(v )) ∪ {v, v }.
As an example, consider the QCN N and an accompanying graph as described in Figure 4. The neighbourhood of C(x 1 , x 3 ) is the induced subgraph of the set of vertices {x 1 , x 2 , x 3 , x 4 }.

With the aforementioned definition in mind, we can define the notion of neighbourhood ◆ G -consistency as follows:

Definition 8. Given a QCN N = (V, C) and a graph G = (V , E), where V ⊆ V , N is said to be neighbourhood ◆ G -consistent, or N ◆ G -consistent for short, if and only if N is G -consistent and ∀{v, v } ∈ E and ∀b ∈ C(v, v ) we have that C (v, v ) = {b}, where (V, C ) = G N(vv ) (N [v,v ]/{b} ).
Similarly, we can define the notion of neighbourhood ◆ ∪ G -consistency as follows:

x 1 x 2 x 3 x 4 x 5 {di, m} {m, si} {o} {pi, p, si, f } {d} {d, o} {eq, d, f i} {d, di} B B
Figure 4: Given the QCN N = (V, C) above and the graph G that results by removing the edge {x 1 , x 5 } from the complete graph on V , we have that

N is neighbourhood ◆ ∪ G -consistent (and neighbourhood ◆ G -consistent), but not ◆ G -consistent (or ◆ ∪ G -consistent) Definition 9. Given a QCN N = (V, C) and a graph G = (V , E), where V ⊆ V , N is said to be neighbourhood ◆ ∪ G -consistent, or N ◆ ∪ G -consistent for short, if and only if N is N ◆ G -consistent and ∀{v, v } ∈ E, ∀b ∈ C(v, v ), and
∀{u, u } ∈ E we have that ∃b ∈ C(u, u ) such that b ∈ C (v, v ), where (V, C ) = G N(vv ) (N [u,u ]/{b } ).
The reader can note that Definitions 8 and 9 mirror Definitions 5 and 6 respectively, the difference being that the closure under G -consistency is restricted to the neighbourhood of the constraint at hand. We recall the following result from [START_REF] Sioutis | Collective Singleton-Based Consistency for Qualitative Constraint Networks[END_REF] in our effort here to build a strengthbased hierarchy among all discussed consistencies: Proposition 1 ( [START_REF] Sioutis | Collective Singleton-Based Consistency for Qualitative Constraint Networks[END_REF]). ◆ ∪ G -consistency is strictly stronger than ◆ G -consistency. In the sequel, Figure 4 will be crucial in proving some results that follow.

N ◆ ∪ G -consistent and N ◆ G -consistent, but not ◆ G -consistent or ◆ ∪ G -consistent.
Specifically, in order for the QCN to become ◆ ∪ G -consistent and ◆ G -consistent, the base relation mi needs to be removed from C(x 2 , x 5 ). In addition, by the definitions of ◆ ∪ G -consistency and N ◆ ∪ G -consistency, we have that every

◆ ∪ G -consistent QCN is N ◆ ∪ G -consistent. Specifically, given a QCN N and two graphs G and G such that G ⊆ G, it holds that if N is G -consistent then N is G -consistent.
Following the same line of reasoning as that of the proof of Proposition 2, we assert the next result:

◆ G -consistent (and neighbourhood ◆ G -consistent), but not neighbourhood ◆ ∪ G -consistent (or ◆ ∪ G -consistent)
Proposition 3. ◆ G -consistency is strictly stronger than N ◆ G -consistency. We proceed with presenting the next result:

Proposition 4. N ◆ ∪ G -consistency is strictly stronger than N ◆ G -consistency. Proof. Consider the QCN along with its accompanying graph depicted in Fig- ure 5. It is the case that the QCN is N ◆ G -consistent, but not N ◆ ∪ G -consistent.
Specifically, in order for the QCN to become N ◆ ∪ G -consistent, the base relation d needs to be removed from C(x 1 , x 2 ). Additionally, by definition of N ◆ ∪ G -consistency, we have that every

N ◆ ∪ G -consistent QCN is N ◆ G -consistent.
We continue with another result as follows:

Proposition 5. N ◆ ∪ G -consistency is incomparable to ◆ G -consistency.
Proof. Consider again the QCN along with its accompanying graph depicted in Figure 5. For the same reason remarked in the proof of Proposition 4, it is the case that the QCN is ◆ G -consistent, but not N ◆ ∪ G -consistent. On the other hand, as noted in the proof of Proposition 2, the QCN of Figure 4 is N ◆ ∪ G -consistent, but not ◆ G -consistent, with respect to its accompanying graph.

From Propositions 2 and 4 (or 1 and 3) we obtain the following result:

Corollary 1. ◆ ∪ G -consistency is strictly stronger than N ◆ G -consistency. To complete our strength-based hierarchy we close off with some results that involve the non-singleton-style consistencies G -consistency and ← -G -consistency. Proposition 6. N ◆ G -consistency is strictly stronger than G -consistency.

Proof. Consider the QCN depicted in Figure 6. As noted in the caption of the figure, the QCN is G -consistent, but not N ◆ G -consistent. Specifically, in order for the QCN to become N ◆ G -consistent, the base relation eq needs to be removed from C(x 2 , x 3 ). Notably, applying N ◆ G -consistency on that QCN makes it minimal. Additionally, by definition of N ◆ G -consistency, we have that every

N ◆ G -consistent QCN is G -consistent.
G -consistent, but not neighbourhood ◆ G -consistent
From Propositions 1, 2, 3, 4, and 6 we obtain the following result:

Corollary 2. Each of the consistencies of ◆ ∪ G -consistency, N ◆ ∪ G -consistency, ◆
G -consistency, and N ◆ G -consistency is strictly stronger than G -consistency. From [START_REF] Sioutis | Leveraging Variable Elimination for Efficiently Reasoning about Qualitative Constraints[END_REF] we have the following result:

Proposition 7 ([53]). G -consistency is strictly stronger than ← - G -consistency.
From Corollary 2 and Proposition 7 we obtain the following last result with regard to our strength-based hierarchy: A visual representation of the established strength-based hierarchy of consistencies is shown in Figure 7. Finally, let the complete graph on a set of variables V be denoted by K V , we have the following remark:

Corollary 3. Each of the consistencies of ◆ ∪ G -consistency, N ◆ ∪ G -consistency, ◆ G -consistency, N ◆ G -consistency,
◆ ∪ G N ◆ ∪ G ◆ G N ◆ G G ← - G
Remark. N ◆ ∪ K V -consistency and ◆ ∪ K V -consistency, respectively N ◆ K V -consistency and ◆ K V -consistency, are equivalent.
The above remark can facilitate the implementation of algorithms for applying the discussed neighbourhood singleton-style consistencies in the case where a complete graph is known to be used, as data structures and operations pertaining to neighbourhoods of relations need not be accounted for.

Algorithm 1: PSWC ∪ N (N , G) in : A QCN N = (V, C), and a graph G = (V ⊆ V, E). out : A sub-QCN of N . 1 begin 2 N ← G (N ); 3 Q ← list(E); 4 while Q = ∅ do 5 {v, v } ← Q.pop(); 6 (V, C ) ← ⊥ V ; 7 foreach b ∈ C(v, v ) do 8 (V, C ) ← (V, C ) ∪ G N(vv ) (N [v,v ]/{b} ); 9 if (V, C ) ⊂ N then 10 f lag ← False; 11 foreach {u, u } ∈ E do 12 if C (u, u ) ⊂ C(u, u ) then 13 C(u, u ) ← C (u, u ); 14 C(u , u) ← C (u , u); 15 f lag ← True; 16 if f lag then 17 Q ← list(E) 18 return N ;

Algorithms and Complexities

For the sake of completeness, we present in this section algorithms PSWC ∪ N and PSWC N , shown in Algorithms 1 and 2 respectively, which given a QCN N and a graph G as input apply N ◆ ∪ G -consistency and N ◆ G -consistency on N respectively. By dropping the red underlined parts in the aforementioned algorithms, the reader can verify that they fall back to algorithms PSWC ∪ and PSWC respectively, which were introduced in [START_REF] Sioutis | Collective Singleton-Based Consistency for Qualitative Constraint Networks[END_REF]. As the latter algorithms have been proven to terminate and return ◆ ∪ G (N ) and ◆ G (N ) respectively given a QCN N = (V, C) and a graph G = (V, E), we can assert the following result: Proposition 8. Given a QCN N = (V, C) and a graph G = (V , E), where V ⊆ V , we have that algorithms PSWC ∪ N and PSWC N terminate and return

N ◆ ∪ G (N ) and N ◆ G (N ) respectively.
Given a QCN N = (V, C) and a graph G = (V , E), where V ⊆ V , the worstcase time complexity for both PSWC ∪ N and

PSWC N is O(α|B| 2 |E| 2 )
, where α is the worst-case time complexity for computing G (N ) with respect to the largest graph G ⊆ G that is used in Line 8 of the algorithms (as each constraint defines its own neighbourhood G ). For any given QCN N = (V, C) and a graph G = Algorithm 2: PSWC N (N , G)

in : A QCN N = (V, C), and a graph G = (V ⊆ V, E). out : A sub-QCN of N . 1 begin 2 N ← G (N ); 3 Q ← list(E); 4 while Q = ∅ do 5 {v, v } ← Q.pop(); 6 (V, C ) ← ⊥ V ; 7 foreach b ∈ C(v, v ) do 8 (V, C ) ← (V, C ) ∪ G N(vv ) (N [v,v ]/{b} ); 9 if C (v, v ) ⊂ C(v, v ) then 10 C(v, v ) ← C (v, v ); 11 C(v , v) ← C (v , v); 12 Q ← list(E); 13 return N ; (V , E), where V ⊆ V , we note that α is O(∆|B||E|)
, where ∆ is the maximum vertex degree of G [START_REF] Chmeiss | Consistency of Triangulated Temporal Qualitative Constraint Networks[END_REF].

Finally, given a QCN N and a graph G, a parsimonious variant for approximating N ◆ ∪ G -consistency in N is algorithm PSWC ∪ N , shown in Algorithm 3. Again, by dropping the red underlined parts in the aforementioned algorithm, the reader can verify that it falls back to a slight generalization of algorithm PSWC ∪ , which was introduced in [START_REF] Sioutis | A Lazy Algorithm to Efficiently Approximate Singleton Path Consistency for Qualitative Constraint Networks[END_REF]. Specifically, contrary to the algorithm as it appears in [START_REF] Sioutis | A Lazy Algorithm to Efficiently Approximate Singleton Path Consistency for Qualitative Constraint Networks[END_REF], in the input of Algorithm 3 we allow any subset S of the set of edges of the input graph to be used; this subset serves as the seed of constraints from which the singleton checks will start propagating themselves. Algorithm PSWC ∪ N is lazy in the sense that it relies upon previously revised constraints to allow itself to continue propagation. Therefore, depending on the subset S to be used, and the order in which the constraints are processed, the algorithm may produce different outputs for the same input (see [START_REF] Sioutis | A Lazy Algorithm to Efficiently Approximate Singleton Path Consistency for Qualitative Constraint Networks[END_REF]). However, we can still relate the output of PSWC ∪ N to the strength-based hierarchy of consistencies for QCNs presented earlier with the following result:

Proposition 9. Given a QCN N = (V, C), a graph G = (V , E)
, where V ⊆ V , and a set S, where S ⊆ E, we have that PSWC ∪ N terminates and returns a sub-QCN N of N such that

N ◆ ∪ G (N ) ⊆ N ⊆ G (N ) respectively.
Proof. In line 2 of the algorithm, the original QCN N is made G -consistent. First, we need to show that the rest of the refinement operations in the algorithm entail G -consistency as well. As G -consistency is closed under union (see [START_REF] Sioutis | Collective Singleton-Based Consistency for Qualitative Constraint Networks: Theory and Practice[END_REF] for more details), the QCN { G N(vv Dataset. We used the dataset employed in [START_REF] Sioutis | Collective Singleton-Based Consistency for Qualitative Constraint Networks: Theory and Practice[END_REF]. That dataset comprises 1 000 random and structured QCNs of IA that were created using models A(n, l, d) [START_REF] Nebel | Solving Hard Qualitative Temporal Reasoning Problems: Evaluating the Efficiency of Using the ORD-Horn Class[END_REF] and BA(n, m) [START_REF] Sioutis | An Efficient Approach for Tackling Large Real World Qualitative Spatial Networks[END_REF] respectively. Pertaining to A(n, l, d), there are 100 QCNs of IA of n = 70 variables and with l = 6.5 base relations per non-universal constraint on average, for all values of the average constraint graph degree d from 7 to 12 with a step of 1. Pertaining to BA(n, m), there are 100 QCNs of IA of n = 150

) (N [v,v ]/{b} ) | b ∈ C(v, v )} that
variables for all values of the constraint graph preferential attachment m [64] from 2 to 5 with a step of 1. Finally, regarding the graphs that were given as input to our algorithms, the maximum cardinality search algorithm [START_REF] Tarjan | Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs[END_REF] was used to obtain triangulations of the constraint graphs of our QCNs. The choice of such chordal graphs was not only reasonable but also crucial given their important theoretical and practical implications in qualitative constraint-based spatial and temporal reasoning, as reviewed in [START_REF] Sioutis | Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoning[END_REF]; the use of those graphs itself was inspired by [START_REF] Huang | Decomposition and tractability in qualitative spatial and temporal reasoning[END_REF][START_REF] Huang | Compactness and its implications for qualitative spatial and temporal reasoning[END_REF][START_REF] Li | A divide-and-conquer approach for solving interval algebra networks[END_REF] among other works, where preliminary results pertaining to tree decompositions were established.

Tools. In addition to our implementations of the algorithms that were presented in Section 4, we utilized the following four software tools:2

• Solver, the state-of-the-art reasoner for checking the satisfiability of QCNs of Interval Algebra and RCC8 that was introduced in [START_REF] Sioutis | An Efficient Approach for Tackling Large Real World Qualitative Spatial Networks[END_REF] (and in particular the reasoner called Phalanx in that work);

• Minimizer, our own implementation of the approach for solving the minimal labeling problem of QCNs of Interval Algebra and RCC8 that was first presented in [START_REF] Amaneddine | Efficient Approach to Solve the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints[END_REF];3

• PWC, the state-of-the-art algorithm for applying G -consistency on QCNs of Interval Algebra and RCC8 that was used in [START_REF] Sioutis | An Efficient Approach for Tackling Large Real World Qualitative Spatial Networks[END_REF] (which is a module of the Phalanx reasoner mentioned earlier);

• DPWC, the state-of-the-art algorithm for applying ← -G -consistency on QCNs of Interval Algebra and RCC8 that was introduced in [START_REF] Sioutis | Leveraging Variable Elimination for Efficiently Reasoning about Qualitative Constraints[END_REF] (and in particular the reasoner called Pyrrhus in that work). Results. The results of our experimental evaluation are detailed in Tables 1 and2, where a fraction x y for Solver denotes that it required x seconds of CPU time on average per dataset of network instances during its operation and detected y such instances as being unsatisfiable in total, a fraction x z for Minimizer denotes that it determined z% of base relations to be unfeasible in total, and a fraction x y|z for the rest of the algorithms denotes all the previous information combined together (from the viewpoint of the respective algorithm).

The first thing to note is that Solver has no competition whatsoever in terms of deciding the satisfiability of a network instance. This was expected, as this type of reasoner is tailored to avoid "bad" branches in the search tree and to reach a leaf (i.e., a solution) in the most efficient way possible. On the other hand, when the entire search tree needs to be taken into account, as is the case with Minimizer, the computational task is much more time-consuming; therefore, Minimizer has by far the worst performance among its competitors.

Regarding the singleton-style consistency algorithms, we can note that they of course have an overhead compared to Solver, but they are much faster in general than Minimizer and they can, in many cases, simulate its pruning capability in an almost exact manner. It is worth mentioning that the neighbourhoodfocused singleton-style algorithms PSWC ∪ N , PSWC N , and PSWC ∪ N are around 30% faster in the phase transition region than the standard algorithms PSWC ∪ , PSWC, and PSWC ∪ respectively, whilst retaining much of the good performance characteristics (viz., unfeasible base relations elimination and satisfiability decision) of the latter respectively. The parsimonious variants PSWC ∪ and PSWC ∪ N are up to 6 times faster in the phase transition region than PSWC ∪ and PSWC ∪ N respectively, but detect in general slightly fewer unsatisfiable network instances and eliminate slightly fewer unfeasible base relations respectively as well. We should note that for a given QCN N = (V, C) and a graph G = (V , E), where V ⊆ V , the subset S that was used as input for the parsimonious variants (see Algorithm 3) corresponds to the set of edges E(G( G (N ))), i.e., the set of edges of the constraint graph of G (N ).

Finally, in order to better assess how the different singleton-style consistency algorithms compare with one another, Figure 8 visualizes the efficiency to effectiveness ratios of those algorithms for the datasets considered here. In particular, the efficiency to effectiveness ratio of a singleton-style algorithm is the ratio x z , where, as a reminder, x denotes the seconds of CPU time that were required on average per dataset of network instances during the algorithm's operation, and z denotes the % of base relations in such instances that were detected as being unfeasible in total. Clearly, the smaller the efficiency to effectiveness ratio is, the better it is, as ideally the CPU time should be kept small and the number of unfeasible base relations high. The discussion here ties in with the remark in the introduction about the sweet spot between effectiveness and efficiency that can be uncovered using neighbourhood-based restrictions in singleton-style consistencies. It is critical to investigate whether such ratios are at all improved by such restrictions, and if so, by how much. As it can be observed in the graphs of Figure 8, it appears to be well worth investing in neighbourhood-based restrictions, since they improve the efficiency to effectiveness ratios of the involved standard algorithms by up to around 25% with 495 respect to both datasets. Taking additionally into account the fact that the effec-tiveness of neighbourhood-focused singleton-style algorithms can only decrease with regard to the respective standard variants (but the same is not true for their efficiency in general), viewing more closely the ratios in Figure 8 suggests that neighbourhood-focused singleton-style algorithms consistently gain much more in efficiency than they lose in effectiveness with regard to the respective standard variants.

Synopsis.

In conclusion, and with respect to the datasets involved here, we observe that the considered singleton-style consistency algorithms are not good options for just checking the satisfiability of a network instance, as they present an overhead when compared to a state-of-the-art reasoner that is tailored to this specific task. However, we also point out that they are ideal candidates for efficiently approximating and even determining in many cases the minimal labeling of a network instance; this becomes even more prominent if one considers the comparatively bad pruning capability of PWC, and the even worse one of DPWC for that matter. It should be noted that even if the state-of-the-art reasoner Minimizer is provided with a minimal network instance (as it was usually the case in our evaluation due to the preprocessing with ◆ ∪ G -consistency, see again Footnote 3 about this), it is an NP-hard problem to decide the satisfiability of that instance, and an NP-hard problem to verify its minimality as a consequence [START_REF] Liu | Solving Minimal Constraint Networks in Qualitative Spatial and Temporal Reasoning[END_REF].

We emphasize again the fact that the neighbourhood-focused singleton-style algorithms PSWC ∪ N , PSWC N , and PSWC ∪ N were found to be around 30% faster in the phase transition region than the standard algorithms PSWC ∪ , PSWC, and PSWC ∪ respectively, for both random and structured QCNs, whilst they were able to retain much of the good performance characteristics in terms of unfeasible base relations elimination and satisfiability decision of the latter respectively. Regarding the parsimonious variants in particular, viz., PSWC ∪ and PSWC ∪ N , even though they exhibited arguably impressive performance characteristics, a major disadvantage is that they do not yield unique closures for a same QCN (see again the discussion in the previous section), which inhibits their theoretical study. Our efficiency to effectiveness ratio analysis revealed that it is well worth investing in neighbourhood-based restrictions, since they were found to improve the efficiency to effectiveness ratios of the involved standard algorithms by up to around 25% with respect to both datasets.

Related Works and Discussion

Singleton-based consistencies belong to the class of strong filtering techniques for both qualitative and traditional constraint-based reasoning. They have been shown to drastically reduce the search space and, thus, improve the performance of solvers for many difficult instances. However, they can suffer from a serious drawback; they are in general too expensive when applied exhaustively during the whole search. For this reason, several researchers worked on proposing either weaker variants of the classic Singleton Arc Consistency (SAC) [START_REF] Debruyne | Some Practicable Filtering Techniques for the Constraint Satisfaction Problem[END_REF][START_REF] Bessière | Theoretical analysis of singleton arc consistency and its extensions[END_REF] or approximation techniques (i.e., techniques that do not reach a fixed point). Regarding the former, several weaker consistencies than SAC have been proposed, with Neighbourhood Singleton Arc Consistency (NSAC) being the main representative [START_REF] Wallace | SAC and Neighbourhood SAC[END_REF]. In NSAC, the AC-based singleton checks are applied only on the sub-graph that corresponds to the neighbourhood of the variable that is being considered, instead of the full graph. This restricted form of SAC, is nearly as effective as SAC in terms of pruning, whilst requiring much less time. NSAC can be seen as a family of consistencies, since it can be generalized by a parameter k (k-NSAC) that fixes the distance from a singleton-checked variable [START_REF] Wallace | Neighbourhood SAC: Extensions and new algorithms[END_REF]. When k = 1, then 1-NSAC is simply referred to as NSAC, and for k = n it is the case that NSAC becomes SAC. Both weaker and stronger consistencies than NSAC have been proposed, for example, by restricting AC to a one pass application on the neighbourhood of a considered variable during a singleton check [START_REF] Paparrizou | On Neighborhood Singleton Consistencies[END_REF], or by replacing AC with a stronger consistency [START_REF] Stergiou | Neighborhood singleton consistencies[END_REF]. In this work, the presented consistencies of N ◆ ∪ G -consistency and N ◆ G -consistency can be seen as adaptations of NSAC to handle infinite domains and qualitative relations. Regarding N ◆ ∪ G -consistency in particular, it is an even closer adaptation for QCNs of neighbourhood-focused 1-partitioning consistency (POAC) [START_REF] Bennaceur | Partition-k-AC: An Efficient Filtering Technique Combining Domain Partition and Arc Consistency[END_REF] for CSPs, with POAC being a stronger variant of SAC (cf. [START_REF] Woodward | Cycle-Based Singleton Local Consistencies[END_REF]). Indeed, as the variables in QCNs contain infinite values, singleton checks involve the base relations that make up a (qualitative) constraint instead. Even though we currently do not parameterize on the distance from a singleton-checked constraint, i.e., on how far its neighbourhood extends away from it, we do parameterize on the graph G that is used for enforcing a given consistency. As noted in Section 5, the choice of G can have important theoretical and practical implications in qualitative constraint-based spatial and temporal reasoning [START_REF] Sioutis | Studying the use and effect of graph decomposition in qualitative spatial and temporal reasoning[END_REF]. Furthermore, AC always holds in a given QCN by the very definition of the latter (see also the discussion about base relations in the beginning of Section 2), and hence we typically utilize a stronger base consistency, namely, G -consistency.

Regarding the approximation techniques of singleton-based consistencies, adaptive variants of POAC have been proposed recently [START_REF] Balafrej | Adaptive Singleton-Based Consistencies[END_REF]; in short, adaptive POAC, referred to as APOAC, is not needed to run until having proved its theoretical fixed point. Balafrej et al. in [74] propose to limit and adapt the number of times that variables are singleton checked, by measuring, during search, the stagnation in the amount of pruned values. The experiments have shown that APOAC can obtain significant speed-ups over SAC and (full) POAC. The bulk of works alternate between two or several levels of consistency to avoid the prohibitive cost of applying a strong consistency either on the entire network as a preprocessing step [START_REF] Paparrizou | Evaluating Simple Fully Automated Heuristics for Adaptive Constraint Propagation[END_REF][START_REF] Balafrej | Adaptive Parameterized Consistency[END_REF][START_REF] Woodward | Adaptive Parameterized Consistency for Non-binary CSPs by Counting Supports[END_REF] or along search [START_REF] Balafrej | Multi-Armed Bandits for Adaptive Constraint Propagation[END_REF]. The parsimonious approach that we presented here, namely, PSWC ∪ N , is closer to the approach of [START_REF] Paparrizou | Evaluating Simple Fully Automated Heuristics for Adaptive Constraint Propagation[END_REF], where a strong consistency is applied only on the constraints that caused a failure during search. Similarly, our method is based on observing where fruitful pruning takes place (during one call of the algorithm), thus revising only constraints whose relations were previously reduced via the elimination of unfeasible base relations.

Arguably, qualitative spatial and temporal reasoning is an area where similar consistencies play a major role in both efficiently solving existing problems and opening new directions by allowing harder problems to be defined and tackled.

Conclusion and Future Work

We proposed singleton-style consistencies for QCNs that are applied just on the neighbourhood of a singleton-checked constraint instead of the whole network, and attained a strength-based hierarchy among all discussed consistencies here. Further, we proposed algorithms to enforce our consistencies, as well as parsimonious variants thereof, that were shown to be much more efficient in practice than the state-of-the-art algorithms for a dataset comprising random and structured QCNs of Interval Algebra. It should be noted that our approach is generic and applies to other calculi as well, such as the spatial calculus RCC8.

Future work consists in obtaining structure-based tractability results focused on the neighbourhood of constraints, developing faster inference mechanisms that will only partially singleton-check a constraint (i.e., only some of the base relations of a constraint will be used for singleton checks), much like quick shaving [START_REF] Lhomme | Quick Shaving[END_REF], establishing adaptive constraint propagators for QCNs (see [START_REF] Balafrej | Adaptive Singleton-Based Consistencies[END_REF] for instance in the context of CSPs), and looking into prioritizing or even solely focusing on singleton checks for base relations that play a crucial role in the computational properties of a given qualitative constraint language [START_REF] Jonsson | Why are CSPs Based on Partition Schemes Computationally Hard?[END_REF][START_REF] Bodirsky | Classification Transfer for Qualitative Reasoning Problems[END_REF]. Therefore, we argue that our approach can drive both theoretical and practical future research and provide a foundation for further work in the study of QCNs, which are pertinent in Symbolic AI [START_REF] Dylla | A Survey of Qualitative Spatial and Temporal Calculi: Algebraic and Computational Properties[END_REF]. The results of this evaluation are detailed in Table A. [START_REF] Bhatt | Geospatial Narratives and Their Spatio-Temporal Dynamics: Commonsense Reasoning for High-Level Analyses in Geographic Information Systems[END_REF], where a fraction n b denotes that the reasoner visited n nodes and produced a search tree with a branching factor of b on average, and in Figure A.9, where cactus plots on the most difficult instances are presented. The average CPU time is analogous to n, i.e., x% of less (or more respectively) visited nodes translates to roughly x% of less (or more respectively) CPU time. The results suggest that there is a boost of about 22% and 7% in the phase transition for instances of Table 1 (d = 10) and Table 2 (m = 4) respectively. These gains are maintained for the most difficult instances too, as it is demonstrated in Figure A.9; specifically, there is a gain of about 22% and 6% for the 5 th percentile of most difficult instances of Table 1 and Table 2 respectively (the distribution is heavy-tailed for both datasets). Finally, by viewing in particular the verification line in Figure A.9, we can see that gains are maxed out for instances of Table 2 (with respect to how Minimizer is in its current form), whereas there is still a lot of room for improvement for instances of Table 1. Such an improvement could be achieved via a tighter integration between one or more singleton-style consistencies and Minimizer (e.g., during search), as the singleton-style consistency is currently only used as a preprocessing step and as a verification subroutine for the special case where it is complete for deciding minimality. G -consistency was not used as a preprocessing step and the input QCN was left untreated, and verification suggests that the input QCN was minimized beforehand (we remind the reader that verifying the minimality of a minimal QCN is already NP-hard [START_REF] Liu | Solving Minimal Constraint Networks in Qualitative Spatial and Temporal Reasoning[END_REF])

Figure 1 :

 1 Figure 1: A QCN in simplified form

- 1 =

 1 {b -1 | b ∈ r}. The weak composition ( ) of two base relations b, b ∈ B is defined as the smallest (i.e., strongest) relation r ∈ 2 B that includes b • b , or, formally, b b ={b ∈ B | b ∩(b • b ) = ∅}, where b • b ={(x, y) ∈ D × D | ∃z ∈ D such that (x, z) ∈ b and (z, y) ∈ b } is the (true) composition of b and b . For all r, r ∈ 2 B , we have that r r = {b b | b ∈ r, b ∈ r }.

Figure 2 :

 2 Figure 2: The base relations of IA; •i denotes the converse of •

Figure 3 :

 3 Figure 3: Figurative examples of QCN terminology using IA

Proposition 2 .

 2 ◆ ∪ G -consistency is strictly stronger than N ◆ ∪ G -consistency. Proof. Consider the QCN along with its accompanying graph depicted in Figure 4. As noted in the caption of the figure, the QCN is

Figure 5 :

 5 Figure 5: Given the QCN N = (V, C) above and the complete graph onV , we have that N is ◆ G -consistent (and neighbourhood ◆ G -consistent), but not neighbourhood ◆ ∪ G -consistent (or

Figure 6 :

 6 Figure 6: Given the QCN N = (V, C) above and the complete graph on V , we have that N is

  and G -consistency is strictly stronger than

Figure 7 :

 7 Figure 7: A strength-based hierarchy of consistencies for QCNs; an arrow denotes the (transitive) strictly stronger relationship and a dotted line the (symmetric) incomparable relationship

  Efficiency to effectiveness ratio pertaining to results of Table1

  Efficiency to effectiveness ratio pertaining to results of Table2

Figure 8 :

 8 Figure 8: Efficiency to effectiveness ratios of singleton-style consistency algorithms

  Insight into the 5 th percentile of most difficult instances of Table1

  Insight into the 5 th percentile of most difficult instances of Table2

Figure A. 9 :

 9 Figure A.9: Insight into the most difficult instances for Minimizer, where suffix * suggests that ◆ ∪

  or inference) capability of different consistencies. Let φ G and ψ G be two consistencies defined by some operations φ and ψ respectively and a graph G. Then, φ G is stronger than ψ G if and only if whenever φ G holds on a QCN N with respect to a graph G, ψ G also holds on N with respect to G, and φ G is strictly stronger than ψ G if and only if φ G is stronger than ψ G and there exists at least one QCN N and a graph G such that ψ G holds on N with respect to G, but φ G does not hold on N with respect to G. (The terms weaker and strictly weaker can be defined likewise.) Finally, φ G and ψ G are incomparable if and only if there exist QCNs N and N such that φG is strictly stronger than ψ G with respect to N and some graph G, and φ G is strictly weaker than ψ G with respect to N and some graph G (we note that the graph G can be different in the two cases). Finally,

	φ G and ψ G are equivalent if and only if we have that φ G is both stronger and weaker than ψ

Table 1 :

 1 Evaluation with random IA networks that were generated using model A(n = 70, l = 6.5, d)[START_REF] Nebel | Solving Hard Qualitative Temporal Reasoning Problems: Evaluating the Efficiency of Using the ORD-Horn Class[END_REF]

	DPWC	0.00s	2|2.48%	0.00s	3|3.70%	0.00s	0|0.63%	0.00s	1|1.92%	0.00s	5|6.07%	0.00s	4|5.09%
	PWC	0.00s	2|3.77%	0.00s	4|7.23%	0.01s	1|4.82%	0.01s	5|10.02%	0.01s	31|34.93%	0.01s	44|47.91%
	PSWC N	2.72s	2|3.84%	9.64s	5|8.64%	20.96s	6|11.36%	36.58s	51|56.45%	10.83s	97|97.06%	1.51s	100|100%
	PSWC	3.00s	2|3.84%	11.22s	5|8.72%	28.23s	6|12.31%	48.04s	54|64.11%	8.44s	99|98.97%	0.70s	100|100%
	PSWC ∪ N	0.40s	2|3.84%	1.58s	5|8.66%	3.41s	6|11.44%	5.46s	44|49.93%	2.57s	91|91.40%	0.79s	100|100%
	PSWC ∪	0.44s	2|3.84%	1.96s	5|8.69%	4.69s	6|12.03%	7.71s	50|57.82%	2.52s	96|96.13%	0.58s	100|100%
	PSWC ∪ N	2.27s	2|3.84%	7.80s	5|8.68%	17.47s	6|11.69%	31.15s	51|57.06%	8.23s	97|97.06%	0.96s	100|100%
	d Solver Minimizer PSWC ∪	7 0.16s 2 12.29s 3.84% 2.54s 2|3.84%	8 0.17s 5 27.40s 8.75% 9.92s 5|8.72%	9 0.29s 6 281.59s 13.67% 24.80s 6|12.31%	10 1.77s 55 1 541.88s 70.57% 41.13s 54|64.13%	11 4.52s 100 5.99s 100% 6.98s 99|98.97%	12 0.23s 100 0.96s 100% 0.59s 100|100%

Table 2 :

 2 Evaluation with structured IA networks that were generated using model BA(n = 150, m)[START_REF] Sioutis | An Efficient Approach for Tackling Large Real World Qualitative Spatial Networks[END_REF]

	DPWC	0.00s	2|2.26%	0.00s	4|3.92%	0.00s	12|12.06%	0.00s	29|28.91%
	PWC	0.00s	2|3.12%	0.01s	7|8.82%	0.01s	42|44.61%	0.01s	92|92.32%
	PSWC N	0.56s	2|3.14%	10.14s	7|9.38%	94.51s	60|65.77%	0.07s	100|100%
	PSWC	0.67s	2|3.14%	12.40s	7|9.42%	126.69s	60|66.83%	0.05s	100|100%
	PSWC ∪ N	0.10s	2|3.14%	1.91s	7|9.40%	19.39s	60|66.24%	0.06s	100|100%
	PSWC ∪	0.12s	2|3.14%	2.52s	7|9.41%	26.06s	60|66.64%	0.06s	100|100%
	PSWC ∪ N	0.45s	2|3.14%	7.85s	7|9.40%	69.81s	60|66.39%	0.07s	100|100%
	m Solver Minimizer PSWC ∪	2 0.15s 2 6.57s 3.14% 0.53s 2|3.14%	3 0.17s 7 34.95s 9.42% 9.55s 7|9.42%	4 0.23s 60 101.33s 66.89% 95.64s 60|66.83%	5 0.16s 100 0.71s 100% 0.04s 100|100%

  Table A.3: Evaluation of Minimizer, where suffix * suggests that ◆ ∪ G -consistency was not used as a preprocessing step and the input QCN was left untreated (a) Evaluation with instances of Table 1

				(b) Evaluation with instances of Table 2
	d Minimizer * Minimizer	m Minimizer * Minimizer
	7	45.02k 1.01	44.90k 1.00	2	143.65k 1.00	143.64k 1.00
	8	41.96k 1.06	41.64k 1.05	3	196.70k 1.00	197.18k 1.00
	9	202.27k 1.74	155.68k 1.67	4	92.13k 1.08	85.29k 1.02
	10	1 096.83k 1.99	852.33k 1.98	5	0.00k 2.12	0.00k 3.23
	11	1.94k 2.00	0.23k 2.01
	12	0.05k 2.07	0.01k 2.57

Clearly, in special cases notions like k-consistency can be defined and exploited theoretically[START_REF] Bodirsky | RCC8 is polynomial on networks of bounded treewidth[END_REF], but these can be hardly implemented efficiently and are therefore not suitable for applications.

These software tools are available at https://msioutis.gitlab.io/software.

In particular, we ported the code to Python and included all recent advances that are associated with the components that comprise that approach, such as improvements in its underlying satisfiability checking module. It must also be noted that the strongest of the local consistencies discussed here, viz., ◆ ∪ G -consistency, was used as a preprocessing step to enhance the performance of Minimizer.

Funding: This work was supported by the Academy of Finland [grant numbers 251170, 327352].

Further, since G (N ) is the unique ⊆-maximal G -consistent sub-QCN of N , it follows that N ⊆ G (N ). Finally, the fact that PSWC ∪ N terminates and returns a sub-QCN N of N such that N ◆ ∪ G (N ) ⊆ N follows directly from the structure of algorithm PSWC ∪ N , which considers a subset of the set of neighbourhoodrestricted collective singleton checks that is performed by PSWC ∪ N .

The worst-case time complexity of PSWC ∪ N is the same as that of PSWC ∪ N (and PSWC N ), although we will see later on in Section 5 that it can be much faster in practice.

Experimental Evaluation

In this section we investigate the utility of the proposed neighbourhood singleton-style consistency algorithms, as well as the discussed state-of-the-art local consistency algorithms that appear in the literature, with respect to the fundamental reasoning problems of satisfiability checking and minimal labeling that are associated with QCNs. Specifically, we explore their effectiveness and efficiency in determining the satisfiability of a given network instance and in discovering the unfeasible base relations of that network instance (in regard to both CPU time and correctness of decision).

Appendix A. Insight into Minimizer

In relation to Section 5, and Footnote 3 specifically, we provide insight into how one of the minimal labeling approximation consistencies, ◆ ∪ G -consistency, boosts the performance of Minimizer. We note that any of the singleton-style consistencies discussed here yields virtually indistinguishable results with respect to enhancing the performance of Minimizer, but we opt for ◆ ∪ G -consistency because it is the most effective one in characterizing unfeasible base relations, and because efficiency is not a factor in this setting (Minimizer is much slower than any of the related algorithms, see Tables 1 and2).