Since we do not have direct result in a manner we would have liked, we will instead analyse the trained models to see if there are relevant insights to be found. For this we looked at models using different aggregation functions, trained on the AIFB dataset.

While we have no intersections between query boxes and target boxes, we could still look whether the target boxes (from T ) appear relatively close to the entity boxes, when compared to the box representations of entities in V−T . This effectively provides some measure as to whether the produced rankings are good. Table 3 shows these results. While these scores may not indicate state-of-the-art results, they do seem to suggest that the model did at least produce decent nontrivial rankings using the SUM and TM aggregators. This could suggest that further research is indeed in order. The fact that TM outperformed SUM is not surprising considering that it is a more involved method that also takes query diameter into account. This result is also in line with the findings in [4]. A more surprising result is that the MLP method did not seem to perform well at all. This could be a result of a faulty implementation, or an implementation that simply does not work for boxes as is. Overall, the results seem promising.

**Table 3.** Percentage (%) of answers embedded closer to the query box compared to a non answer, with regard to the query structure, using different aggregation function. Tested on AIFB dataset. (Results were earlier reported in [1])

#### **6 Conclusion and Outlook**

In this work, we looked critically at the currently prevailing evaluation strategy for approximate complex structured query algorithms for knowledge graphs. Typically, these systems take a query as an input and produce a ranking of all entities in the KG as an output. The performance of these systems is than determined using metrics typically used in information retrieval.

What we propose is to augment the current evaluations by also requiring these systems to produce a binary classification of the nodes into a class of answers and one of non-answers. This is needed because many applications can simply not work with a ranking and need a fixed set of answers to work with.

As a first proof of concept, we have adapted ideas from MPQE and query2Box, and created an embedding algorithm that represents the queries and the entities as axis-aligned hyper-rectangles. We noticed that the performance of this system is pretty low, and expect that future works can heavily improve upon this first attempt.

As future research directions, we see a need to expand our experiments to include other query types (disjunctions, negations, filters, etc.), in order to show the generalizability of our approach. This will, however, require new representation for the volumes as these operations are not possible if we would stay with just boxes. For example, the negation of a box, would no longer be a box.

Moreover, we it needs to be investigated how our method can be applied on different kinds of graphs. This will give us insights as to what changes need to be made in terms of training data (via query generation) as well as the effects on model performance. Also, it seems worth experimenting with different geometric representations for the parts of the query (anchor, variables and targets). Finally, since our experiments were relatively small-scale, further research could also start by simply experimenting with different settings for our current architecture.

## **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

## **Galois Connections for Patterns: An Algebra of Labelled Graphs**

David A. Cohen1, Martin C. Cooper2(B), Peter G. Jeavons3, and Stanislav Zivn´ ˇ y3

1 Royal Holloway, University of London, Egham, UK<EMAIL_ADDRESS>2 IRIT, University of Toulouse, Toulouse, France<EMAIL_ADDRESS>3 University of Oxford, Oxford, UK<EMAIL_ADDRESS>
**Abstract.** A pattern is a generic instance of a binary constraint satisfaction problem (CSP) in which the compatibility of certain pairs of variable-value assignments may be unspecified. The notion of forbidden pattern has led to the discovery of several novel tractable classes for the CSP. However, for this field to come of age it is time for a theoretical study of the algebra of patterns. We present a Galois connection between lattices composed of sets of forbidden patterns and sets of generic instances, and investigate its consequences. We then extend patterns to augmented patterns and exhibit a similar Galois connection. Augmented patterns are a more powerful language than flat (i.e. nonaugmented) patterns, as we demonstrate by showing that, for any k ≥ 1, instances with tree-width bounded by k cannot be specified by forbidding a finite set of flat patterns but can be specified by a finite set of augmented patterns. A single finite set of augmented patterns can also describe the class of instances such that each instance has a weak nearunanimity polymorphism of arity k (thus covering all tractable language classes).We investigate the power of forbidding augmented patterns and discuss their potential for describing new tractable classes.

**Keywords:** Constraint satisfaction · Tractability · Forbidden patterns · Galois connection · Lattice

The authors were supported by EPSRC grant EP/L021226/1. Martin Cooper was supported by the grants ANR-18-CE40-0011 and ANR-19-PI3A-000. Stanislav Zivn´ ˇ y was supported by a Royal Society University Research Fellowship. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 714532). The paper reflects only the authors' views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein.

#### **1 Introduction**

The CSP (Constraint Satisfaction Problem) is a classical abstract framework for the modelling of finite-domain constrained assignment problems [8,32]. Although first inspired by applications in computer vision and artificial intelligence, it's generic nature has allowed it to become a programming paradigm in its own right used in, for example, scheduling, product configuration, planning and bioinformatics. It is well known that the CSP is NP-complete and remains so even when restricted to binary constraints since all instances have an equivalent dual instance which is binary [22,40].

An interesting avenue of theoretical research on CSPs consists in the characterisation of tractable subproblems defined by placing a restriction on the type of constraints that can occur (the constraint language) and again it is known that it is possible to limit attention to languages of binary relations [5,10]. A major advance towards the recent characterisation of tractable constraint languages [3,41] was the algebraic approach based on the study of pointwise closure operations of constraint relations, known as polymorphisms, and the identities satisfied by these polymorphisms [1,4]. Of particular interest is the Galois connection between (sets of) polymorphisms and (sets of) relations [27]. In parallel, tractable subproblems of the CSP based on restrictions on the (hyper)-graph of constraint scopes (the constraint (hyper)graph) were also characterised [26].

In order to define new classes, we need to go beyond placing restrictions on constraint languages or on the structure of the constraint (hyper)-graph. A natural way of defining sets of instances is to consider properties of the microstructure of binary CSP instances [30]. A *pattern* can be seen as a partial microstructure (i.e. a binary CSP instance in which the compatibility of some assignments may be left undefined) or, more abstractly, as a graph with vertices labelled by names of variables and edges which may be positive or negative. Defining sets of binary CSP instances by forbidding patterns has led to the discovery of novel tractable classes [9,18]. For example, in each of the following cases, forbidding a simple 3 variable pattern defines a tractable class of binary CSP instances which strictly generalises a known tractable class:

In this paper we initiate the study of the underlying theory of forbidden (sets of) patterns, an essential foundation on which to build a characterisation of all tractable classes defined by forbidden (sets of) patterns. We begin by studying what we call flat patterns before studying augmented patterns with extra structure, such as partial orders on variables or domain values. Adding such structure is not only essential to define certain hybrid classes such as BTP [16] and EMC [19], but, as we will show in Sect. 6, also allows us to define (families of) polymorphisms [28] and bounded tree-width [20] within the same framework.

For both flat and augmented patterns, we exhibit a Galois connection between sets of patterns and sets of instances. In each case, we investigate the tractability consequences of the Galois connection, including the possibility of defining new tractable classes by combination of known tractable classes via the lattice operations. We notably show that tractable classes form a sublattice.

### **2 Definitions and Notation**

We assume that there is a countable collection of variables X and a countable domain D of values. A variable-value pair (x, a), representing the assignment of value a ∈ D to variable x ∈ X , is known as a *point*. A *flat pattern* (or simply a *pattern*) P = A*P* , ρ*P* is a subset A*P* of X ×D equipped with a (partial) function ρ*P* from the pairs of points (x, a),(y, b) of P such that x = y to {negative, positive}. Thus P consists of a set of variable-value assignments (x, a) together with a set of negative and positive edges representing the compatibility of pairs of assignments. In figures we represent negative edges by dashed lines, positive edges by solid lines and points corresponding to assignments to the same variable are grouped into ovals. Three patterns P1, P2, P3 are shown in Fig. 1.

**Fig. 1.** Examples of the occurrence of a pattern in another pattern: P1 → P2, P2 → P1, P1 → P3, P2 → P3.

We give a recursive definition of connectedness. Two points (x, a),(y, b) in a pattern P are *connected* if x = y or ρ*P* ((x, a),(y, b)) ∈ {negative, positive} or if (x, a),(y, b) are both connected to some point (z, c) of P. Clearly, each pattern has a decomposition into connected components according to this definition of connectedness.

A *completely specified binary CSP instance* (or simply an *instance*) is a pattern I = A*I* , ρ*I* in which the function ρ*I* is total, i.e. the compatibility of each pair of variable-value assignments (to distinct variables) is specified. Given an instance I on n variables, a *solution* to I is a clique of positive edges of size n, which corresponds to a pairwise-compatible assignment of values to variables. The question associated with an instance is the existence of a solution. An instance I is *arc consistent* if for all points (x, a) of I and all variables y = x of I, (x, a) has a support at y, i.e. ∃b ∈ D such that {(x, a),(y, b)} is a positive edge in I.

A pattern P = A*P* , ρ*P occurs* in pattern Q = A*Q*, ρ*Q* if there is a mapping f from A*P* to A*Q* which respects variables, maps negative edges to negative edges and positive edges to positive edges, i.e.

We use the notation P → Q to denote that P *occurs* in pattern Q (and P - Q if it does not). It is easy to see from its definition that occurrence is transitive: P → Q and Q → R implies P → R. We consider two patterns P, Q to be equivalent if P → Q and Q → P: we write P ≈ Q. For example, patterns P1 and P2 in Fig. 1 are equivalent; we notably have P1 → P2 since (x, a), (y, b) can both map to (z, c). Clearly, we have P2 → P3, and then, by transitivity, P1 → P3. For simplicity of presentation, throughout this paper, we will talk about patterns rather than equivalence classes of patterns.

Each pattern P defines a corresponding set of instances in which P does not occur. For example, the pattern P3 of Fig. 1 defines a set of instances which includes all binary CSP instances with Boolean domains, since if P3 → I then the points (v, d), (v, e), (v, f) must map to three distinct values for the same variable in I, due to the positive and negative edges in P3.

Note that in previous work, it has sometimes been convenient to assume that when P occurs in Q, distinct variables of P map to distinct variables of Q [11,15,19]. However, to establish a Galois connection for flat patterns, we require a looser definition of occurrence in which two or more variables of P may map to the same variable in Q. To impose the stricter definition of occurrence (inducing an injective mapping of variables of P), it suffices, for each pair of distinct variables x, y, to add two new points (x, a), (y, b) to A*P* and an extra dummy positive edge between points (x, a), (y, b) in P; this prevents x, y mapping to the same variable in Q (and only changes the semantics of P in a trivial way). A more elegant solution (in order to impose an injective mapping of variables) is to augment the patterns with a not-equal-to relation between variables which is possible in the framework of augmented patterns discussed in Sect. 6.

We consider sets S of patterns. These sets will usually be finite, indeed, often a singleton. When forbidden, a set S of patterns defines a set of instances (those sets of instances in which none of the patterns in S occurs). Such sets T of instances are hereditary in the sense that (I ∈ T) ∧ (I ⊆ I) =⇒ (I ∈ T), where I ⊆ I means (A*I*- ⊆ A*I* ) ∧ (ρ*I*- = ρ*I* |*AI*- ). Many, but not all, classes of interest are hereditary. For example, for any k, the set of instances whose tree-width is bounded by k is hereditary. On the other hand, the set of instances which is arc-consistent is not hereditary, since a value which has a support at another variable in an instance I will not necessarily have a support in I ⊂ I. Thus forbidden flat patterns alone cannot express any class of instances which requires arc consistency (or a higher level of consistency) [36]. Nevertheless, we will see in Sect. 6 how a combination of augmented patterns and filters on instances provides a very expressive language in which to define classes on instances, allowing us to express such classes of instances.

In order to obtain a Galois connection we consider sets of generic instances, where a generic instance can be viewed as a partially-specified instance and is, in fact, again just a pattern. However, the lattice structure on sets of patterns is different depending on whether we view these patterns as partially-specified instances or as forbidden sub-instances. When defining tractability of sets of generic instances we filter instances keeping only those that are completely specified.

**Definition 1.** *A set* T *of generic instances is* tractable *if there is a polynomialtime algorithm which decides all completely-specified instances in* T*. A set* S *of forbidden patterns is tractable if the corresponding set of instances in which none of the patterns in* S *occur is tractable.*

To define lattices of (sets of) instances and (sets of) patterns, we also require the following operation on patterns: if P, Q are patterns, then P + Q is a single pattern consisting of (copies of) the two patterns P and Q (without any common points and without any edges between P and Q). We call this the *juxtaposition* of the two patterns P and Q. Observe that P + P ≈ P (since P + P → P follows from the definition of occurrence which allows us to map the two copies of P to P). If S1, S2 are sets of patterns, then S1 + S2 is the set of patterns {P + Q | P ∈ S1 ∧ Q ∈ S2}.

We also require another operation on pairs of patterns, which can be seen as the greatest lower bound of the two patterns. If P, Q are patterns, then P × Q is a single pattern built by forming the juxtaposition of all patterns R such that (R → P)∧(R → Q). We say that such patterns R are *common factors* of P and Q. We only include patterns R which are maximal in the sense that there is no R ≈ R such that R → R and (R → P) ∧ (R → Q). Observe that including only maximal R, ensures that we have P ×P ≈ P. The operation × is illustrated in Fig. 2. In this example, the patterns P and Q have only two maximal common

**Fig. 2.** The operation P × Q.

factors (modulo the equivalence relation ≈) and P × Q is the juxtaposition of these two common factors. Note that P1 and P2 (shown in Fig. 1) are both common factors of P and Q, but since P1 ≈ P2 we only need to include one of these patterns in P × Q. If S1, S2 are sets of patterns, then S1 × S2 is the set of patterns {P × Q | P ∈ S1 ∧ Q ∈ S2}.

The following lemmas provide a logical interpretation of the + and × operations on patterns.

**Lemma 1.** *For all patterns* P1, P2, I*, we have* P1 +P2 - I *if and only if* (P1 - I ∨ P2 -I)

*Proof.* For all patterns P1, P2, I, P1+P2 → I if and only if (P1 → I ∧P2 → I) by the definition of P1+P2. By contraposition, for all patterns P1, P2, I, P1+P2 - I if and only if (P1 - I ∨ P2 -I).

**Lemma 2.** *For all patterns* P, I1, I2*,* P - I1 × I2 *if and only if* (P - I1 ∨ P - I2)*.*

*Proof.* By contraposition, it suffices to show that P → I1 × I2 if and only if P → I1 ∧ P → I2. If P → I1 ∧ P → I2, then P is a common factor of I1 and I2 and hence P → I1 × I2. On the other hand, if P → I1 × I2, then, due to the lack of edges between the connected components of I1 × I2, P must be the juxtaposition of patterns P1,...,P*r* where for each i = 1,...,r, P*i* → R*i* for some R*i* which is one of the connected components of I1 × I2. Each connected component R*i* of I1 × I2 satisfies R*i* → R *i* for some common factor R *i* of I1 and I2. By transitivity of the occurrence relation and by definition of I1×I2, we have P*i* → I1 and P*i* → I2 (for i = 1,...,r) and hence P → I1 and P → I2.

### **3 The Two Lattices**

Let P be the set of all patterns and I be the set of all generic instances. Let T be the set of all subsets of I. Let S be the set of all subsets of P. In this section we show that S and T have lattice structures with partial orders based on notions of occurrence. Although P = I, S and T are distinct since they do not have the same partial order.

We require two different definitions of occurrence of one set of patterns in another, depending on whether the sets of patterns are considered as forbidden patterns or sets of generic instances. For S1, S2 ∈ S, we write S1 - S2 to mean that ∀Q ∈ S2, ∃P ∈ S1 such that P → Q. We write S1 - S2 if S1 - S2 and S2 - S1. For T1, T2 ∈ T , we write T1 → T2 to mean ∀P ∈ T1, ∃Q ∈ T2 such that P → Q. We write T1 ↔ T2 if T1 → T2 and T2 → T1. It follows directly from their definitions that and ↔ are equivalence relations.

Let T be the set of all equivalence classes (according to ↔) of sets of generic instances. Let S be the set of all equivalence classes (according to -) of sets of forbidden patterns.

It is not difficult to see that → is a partial order on T and that is a partial order on S. It follows that T and S both have a lattice structure [2,21]. The following proposition shows that the set T has a lattice structure with meet and join operations × and ∪, whereas the set S has a lattice structure with meet and join operations + and ∪.

**Proposition 1.** *For all* S1, S2 ∈ S*, (1)* S2 - S1 ⇔ S1 + S2 - S1 *and (2)* S2 - S1 ⇔ S1 ∪ S2 - S2*. For all* T1, T2 ∈ T *, (3)* T1 → T2 ⇔ T1 × T2 ↔ T1 *and (4)* T1 → T2 ⇔ T1 ∪ T2 ↔ T2*.*

*Proof.* (1) ⇒: S2 - S1 means ∀P ∈ S1, ∃Q ∈ S2 such that Q → P and hence P + Q → P. Thus S1 + S2 - S1. Clearly S1 -S1 + S2.

(1) ⇐: S1 + S2 - S1 means ∀P ∈ S1, ∃R + Q ∈ S1 + S2 such that R + Q → P which implies Q → P. Hence S2 -S1.

(2) ⇒: S2 - S1 means ∀P ∈ S1, ∃Q ∈ S2 such that Q → P. Now, since ∀Q, Q → Q, we have ∀R ∈ S1 ∪ S2, ∃Q ∈ S2 such that Q → R. Hence S2 - S1 ∪ S2. Clearly S1 ∪ S2 -S2.

(2) ⇐: S2 - S1 ∪ S2 implies that ∀P ∈ S1, ∃Q ∈ S2 such that Q → P and so S2 -S1.

(3) T1 → T2 means that ∀I ∈ T1, ∃J ∈ T2 such that I → J, so I is a common factor of I and J and hence I → I × J. Thus T1 → T1 × T2. Thus, by definition of ×, T1 × T2 → T1.

(3) ⇐: T1 → T1 × T2 means that ∀I ∈ T1, ∃I × J ∈ T1 × T2 such that each connected component of I occurs in a common factor of I and J, and hence each connected component of I occurs in J and so I → J. Thus T1 → T2.

(4) ⇒: T1 → T2 means ∀I ∈ T1, ∃J ∈ T2 such that I → J. Thus T1 ∪ T2 → T2. Clearly T2 → T1 ∪ T2.

(4) ⇐: T1 ∪ T2 → T2 implies ∀I ∈ T1, ∃J ∈ T2 such that I → J which is exactly T1 → T2.

The following lemmas are not essential for the lattice structure of S and T , but will be useful later.

**Lemma 3.** *If* S1 ⊇ S2 *then* S1 -S2*. If* T1 ⊆ T2 *then* T1 → T2*.*

*Proof.* If S1 ⊇ S2 then ∀Q ∈ S2, ∃P = Q ∈ S1 such that P → Q. If T1 ⊆ T2 then ∀P ∈ T1, ∃Q = P ∈ T2 such that P → Q.

**Lemma 4.** *For all sets of patterns* S1, S2*,* S1 + S2 - S1 ∩ S2 *and* S1 ∩ S2 → S1 × S2*.*

*Proof.* We have ∀P ∈ S1 ∩S2, P - P +P ∈ S1 +S2. Hence S1 +S2 - S1 ∩S2. Also ∀I ∈ S1 ∩ S2, I ↔ I× ∈ S1 × S2. Hence S1 ∩ S2 → S1 × S2.

If we consider that S1 ≤ S2 if S2 - S1, then the minimal element in the lattice S is the empty set of patterns and the maximal element is {P∅} where P∅ is the pattern containing no points or edges. If we consider that T1 ≤ T2 if T1 → T2 then the minimal element of T is the empty set of patterns and the maximal element is the set of all patterns.

The two lattices S and T are both distributive, as shown by the following proposition.

**Proposition 2.** *For all* S1, S2, S3 ∈ S*, we have* S1 + (S2 ∪ S3) - (S1 + S2) ∪ (S1+S3) *and for all* T1, T2, T3 ∈ T *, we have* T1∪(T2×T3) ↔ (T1×T2)∪(T1×T3)*.*

*Proof.* These follow immediately from the definitions.

## **4 The Galois Connection**

The Galois connection is based on two functions f : S→T and g : T →S, defined as follows.

$$\begin{aligned} f(S) &= \{ I \in \mathcal{T} \mid \forall P \in S, P \twoheadrightarrow I \} \\ g(T) &= \{ P \in \mathcal{P} \mid \forall I \in T, P \twoheadrightarrow I \} \end{aligned}$$

**Theorem 1.** *There is an antitone Galois connection between* S *and* T *.*

*Proof.* The functions f,g, applied to equivalence classes of S and T define a Galois connection between S and T if ∀S ∈ S, ∀T ∈ T , T ≤ f(S) ⇔ S ≤ g(T). This corresponds to (T → f(S)) ⇔ (g(T) - S), which holds because (T → f(S)) and (g(T) - S) are both equivalent to ∀P ∈ S, ∀I ∈ T, P - I. We therefore have a Galois connection between S and T .

We now study this Galois connection in more detail.

**Proposition 3.** *For all* S1, S2 ∈ S*, if* S1 - S2 *then* f(S1) ⊆ f(S2)*. For all* T1, T2 ∈ T *, if* T1 → T2 *then* g(T2) ⊆ g(T1)*.*

*Proof.* Suppose S1 - S2. Then ∀P2 ∈ S2, ∃P1 ∈ S1 such that P1 - P2. Consider I ∈ f(S1). By definition of f, ∀P1 ∈ S1, P1 - I. It follows that I ∈ f(S2) since otherwise we would have some P2 ∈ S2 such that P2 → I and some P1 ∈ S1 with P1 → P2 → I which contradicts P1 -I.

Suppose T1 → T2. Then ∀I1 ∈ T1, ∃I2 ∈ T2 such that I1 → I2. Consider P ∈ f(T2). By definition of g, ∀I2 ∈ T2, P - I2. It follows that P ∈ g(T1) since otherwise we would have some I1 ∈ T1 such that P → I1 and some I2 ∈ T2 such that P → I1 → I2 which contradicts P -I2.

We immediately have the following corollary.

**Corollary 1.** *For all* S1, S2 ∈ S*,* S1 - S2 ⇒ f(S1) → f(S2)*. For all* T1, T2 ∈ T *,* T1 → T2 ⇒ g(T1) g(T2)*.*

**Proposition 4.** *For any patterns* S1, S2*,* f(S1) = f(S2) *if and only if* S1 -S2*.*

*Proof.* Suppose f(S1) = f(S2). Then ∀I, (∀P ∈ S1, P - I) ⇔ (∀P ∈ S2, P - I). This is equivalent to ∀I, (∃P ∈ S1, P → I) ⇔ (∃P ∈ S2, P → I). It follows, by setting I = P ∈ S2, that ∀P ∈ S2, ∃P ∈ S1 such that P → P, and hence S1 - S2. By setting I = P ∈ S1, by a symmetrical argument, we obtain S2 - S1, and hence S1 -S2.

Now suppose that S1 - S2. Then, by Proposition 3, we can deduce that f(S1) = f(S2).

It is important to observe that T includes sets of partially-specified instances. If we considered only sets of completely-specified instances in T , then Proposition 4 would not hold. For example, consider S1 and S2 shown in Fig. 3. It is easy to see that we do not have S1 - S2, even though S1 and S2 define the same set of completely-specified instances when forbidden, namely those instances which have only positive edges or only negative edges. They do not define the same set of *generic instances*, since, for example, the single pattern Q ∈ S2 is in f(S1) but not f(S2).

**Proposition 5.** *For any patterns* T1, T2*,* g(T1) = g(T2) *if and only if* T1 ↔ T2*.*

*Proof.* Suppose g(T1) = g(T2). Then ∀P, (∀I ∈ T1, P - I) ⇔ (∀I ∈ T2, P - I). This is equivalent to ∀P, (∃I ∈ T1, P → I) ⇔ (∃I ∈ T2, P → I)). Setting P = I ∈ T1, we obtain ∀I ∈ T1, ∃I ∈ T2 such that I → I , and hence T1 → T2.

**Fig. 3.** The sets of patterns S1 = {P1, P2} and S2 = {Q} define the same set of completely specified instances when forbidden, but f(S1) = f(S2).

Setting P = I ∈ T2, by a symmetrical argument, we obtain T2 → T1, and hence T1 ↔ T2.

Now suppose that T1 ↔ T2. By Proposition 3, we can deduce that g(T1) = g(T2).

We now show to what extent the lattice structure of S and T is preserved via the mappings f and g.

**Theorem 2.** ∀S1, S2 ∈ S*,* f(S1) ∪ f(S2) = f(S1 + S2)*.*

*Proof.* For i = 1, 2, f(S*i*) = {I | ∀P ∈ S*i*, P - I}. So f(S1)∪f(S2) = {I | (∀P ∈ S1, P - I) ∨ (∀P ∈ S2, P - I)} = {I | ∀P1 ∈ S1, ∀P2 ∈ S2(P1 - I ∨ P2 - I)}. Thus, by Lemma 1, f(S1) ∪ f(S2) = {I | (∀P1 ∈ S1, ∀P2 ∈ S2(P1 + P2 - I)} = {I | ∀P1 + P2 ∈ S1 + S2(P1 + P2 -I)} = f(S1 + S2).

**Theorem 3.** ∀S1, S2 ∈ S*,* f(S1) ∩ f(S2) = f(S1 ∪ S2)*.*

*Proof.* f(S1 ∪ S2) = {I | ∀P ∈ S1 ∪ S2, P - I} = {I | ∀P1 ∈ S1, P - I} ∩ {I | ∀P2 ∈ S2, P -I} = f(S1) ∩ f(S2).

The lattice structure and Theorems 2 and 3 are illustrated in Fig. 4.

**Theorem 4.** ∀T1, T2 ∈ T *,* g(T1) ∩ g(T2) = g(T1 ∪ T2)*.*

*Proof.* g(T1 ∪ T2) = {P | ∀I ∈ T1 ∪ T2, P - I} = {P1 | ∀I ∈ T1, P1 - I} ∩ {P2 | ∀I ∈ T2, P2 -I} = g(T1) ∩ g(T2)

**Theorem 5.** ∀T1, T2 ∈ T *,* g(T1) ∪ g(T2) = g(T1 × T2)*.*

**Fig. 4.** The function f from S to T

*Proof.* g(T1 × T2) = {P | ∀I ∈ T1 × T2, P - I} = {P | ∀I1 ∈ T1, ∀I2 ∈ T2, P - I1×I2}. By Lemma 2, this is equal to {P | ∀I1 ∈ T1, ∀I2 ∈ T2,(P - I1∨P - I2)} = {P | ∀I1 ∈ T1, P - I1}∪{P | ∀I2 ∈ T2, P -I2} = g(T1) ∪ g(T2).

Theorems 4 and 5 are illustrated in Fig. 5.

**Definition 2.** *A set* T *of patterns is* downward-closed *if for all patterns* P, Q*,* (P → Q) ∧ (Q ∈ T) ⇒ (P ∈ T)*. A set of patterns* S *is* upward-closed *if for all patterns* P, Q*,* (P → Q) ∧ (P ∈ S) ⇒ (Q ∈ S)*.*

In the case of upward-closed sets of forbidden patterns and/or downwardclosed sets of generic instances, the lattices, and the corresponding Galois connection, become simpler as the following proposition shows. In this case the two lattices become lattices of sets with meet and join operations ∩ and ∪. In practice, however, we are generally interested in small sets of forbidden patterns which cannot be upward-closed (otherwise they would be infinite).

**Proposition 6.** *If* S1, S2 *are upward-closed, then* S1 + S2 - S1 ∩ S2*. If* T1, T2 *are downward-closed, then* T1 ∩ T2 ↔ T1 × T2*.*

*Proof.* ∀P + Q ∈ S1 + S2, we have P → P + Q and Q → P + Q. By the upward closedness of both S1 and S2, it follows that P + Q ∈ S1 ∩ S2. Thus S1 ∩ S2 - S1 + S2. By Lemma 4, we have S1 + S2 -S1 ∩ S2.

**Fig. 5.** The function g from T to S

∀P × Q ∈ T1 × T2, P × Q → P and P × Q → Q. If T1, T2 are downwardclosed, then P × Q ∈ T1 ∩ T2. Thus T1 × T2 → T1 ∩ T2. By Lemma 4, we have T1 ∩ T2 ↔ T1 × T2.

#### **5 Tractability Consequences of the Galois Connection**

In this section we show that tractable sets of patterns form a sublattice of S.

Recall that we say that T ∈ T is tractable if there is a polynomial-time algorithm to decide all completely-specified instances in T. We consider that incompletely-specified instances (i.e. generic instances with at least one pair of points not joined by a (positive or negative) edge) can be recognised as such in polynomial time and hence do not affect the tractability of T. A consequence of this is that it is not true that T1 → T2 ∧ (T2 tractable) ⇒ T1 tractable. For example, T2 could be trivially tractable because it contains no completelyspecified instance even when T1 is the set of all binary CSP instances. However, we have the following important result.

**Proposition 7.** *If* T1 = f(S1) *and* T2 = f(S2)*, then* (T1 → T2 ∧ (T2 *tractable*)) ⇒ T1 *tractable.*

*Proof.* Let T1 = f(S1) and T2 = f(S2), where T1 → T2. By Proposition 3, we have g(T2) ⊆ g(T1) and so by Lemma 3, g(T1) g(T2). By definition of the functions f and g, we have f(g(f(S))) = f(S) for all S, and so f(g(T1)) = f(S1) and f(g(T2)) = f(S2). It follows from Proposition 4 that S1 g(T1) and S2 g(T2). Thus S1 g(T1) g(T2) - S2. By transitivity of -, we have S1 - S2 and, by Proposition 3, T1 = f(S1) ⊆ f(S2) = T2. It follows that if T2 is tractable, then so is T1.

This means that it may be possible to classify the complexity of all classes f(S) for all finite sets S ∈ S. Indeed we conjecture that there is a P/NP-complete dichotomy. This has already been proved for sets of patterns containing only negative edges [9].

The following proposition tells us that the tractable sets of patterns form a sub-lattice of S.

**Proposition 8.** *If* S1, S2 *are tractable sets of patterns, then so are* S1 ∪ S2 *and* S1 + S2*.*

*Proof.* f(S1 +S2) = f(S1)∪f(S2) and hence can be solved in polynomial time if f(S1) and f(S2) can be. A similar remark holds for f(S1 ∪ S2) = f(S1) ∩ f(S2).

We can observe that the finite sets of S form a sublattice of S since S1+S2 and S1 ∪ S2 are finite if S1, S2 are finite. It follows that the finite tractable sets of S form a sublattice. We are particularly interested in finite sets of patterns, since detecting the absence of finite sets of patterns can be achieved in polynomial time, whereas testing the absence of an infinite set of patterns may not even by computable. We can observe that there are infinite sets of patterns S such that f(S) is tractable but for no finite subset S of S is f(S ) tractable, e.g. acyclic instances that can be defined by forbidding cycles of all lengths but by no finite set of flat patterns [11].

## **6 Augmented Patterns: Motivation**

We can make the language of patterns much richer by adding relations to patterns (and possibly quantifying over these relations). A *flat* pattern (the kind of pattern we have studied up to now in this paper) has only the binary relations of compatibility between points (positive edges), incompatibility between points (negative edges) and the equivalence relation between points corresponding to assignments to the same variable (represented in figures by ovals representing its equivalence classes). Suppose that we add a new relation, such as an ordering or a colouring of the points of the pattern. We call this an *augmented pattern*. In this section, we motivate the study of augmented patterns by showing that they can be used to define interesting tractable classes that cannot be defined using flat patterns. Examples of such augmented patterns are a pattern in which we add an ordering between points (the new relation is binary) or a colouring of points (in which case the new relation is unary). For these new relations to be meaningful, they must satisfy the basic properties of, for example, orderings or colourings. To impose this we can replace a single pattern P by a set of patterns, one being the augmented pattern P and the others designed in such a way as to impose the required properties of the new relation.

Consider a binary relation R*<*. Each of the following three statements can be seen as an augmented pattern involving only the relation R*<*:

$$R\_{<}(a,a) \tag{1}$$

$$R\_{<}(a,b) \land R\_{<}(b,a) \tag{2}$$

$$R\_{\leq}(a,b) \land R\_{\leq}(b,c) \land R\_{\leq}(c,a) \tag{3}$$

By forbidding these three patterns, we impose that R*<* is an irreflexive, antisymmetric relation with no length-3 cycles. In the following we only consider instances in which R*<* is total in the sense that for all distinct a, b, we have R*<*(a, b) or R*<*(b, a). It is easy to see that this implies that R*<* is a strict total order (since, in particular, forbidding pattern (3) corresponds to transitivity). From now on, for notational convenience, we use the operator < instead of the relation R*<*, i.e. we write a<b instead of R*<*(a, b). If we also forbid the augmented pattern shown in Fig. 6(a), then we not only impose an order on the points of an instance, but we also impose that there is a corresponding order on the variables which is consistent with this order on the points.

If we also forbid the augmented pattern in Fig. 6(b), then we are saying that there is a total ordering of the variables of the instance such that each variable is constrained by at most one previous variable in this order. The set of completely-specified instances with a total ordering on its points in which none of these five augmented patterns occurs corresponds exactly to the set of instances whose constraint graph is acyclic. It is well known that this class of binary CSP instances is tractable since it is solved by arc consistency [22]. Recall that no finite set of forbidden *flat* patterns defines the set of acyclic instances [11]. This example demonstrates the power of augmented patterns compared to flat patterns, since acyclicity can be defined by forbidding a set of just five augmented patterns.

In fact, for any fixed k ≥ 1, we can define the class of instances with treewidth bounded by k using a finite set of augmented patterns. We saw above that the patterns (1), (2), (3) together with the pattern shown in Fig. 6(a) effectively allows us to impose an order on variables. Apart from this variable-order relation, we also introduce another binary relation *IE* (for Induced Edge between two variables in the constraint graph) which, using the same idea as in Fig. 6(a), is also effectively a relation on variables. For simplicity of presentation, in the following, we apply < and *IE* to variables rather than points. We also require the relation *IE* and we will consider only those instances in which *IE* and *IE* cover all pairs of variables. To ensure that *IE* is the complement of *IE* we forbid the augmented pattern

$$IE(x,y) \land \overline{IE}(x,y)$$

The semantics of the induced-edge relation *IE* is given by the following rules:

**Fig. 6.** Examples of augmented patterns.

3. If x<z, y<z, *IE*(x, z) and *IE*(y, z), then *IE*(x, y).

These rules can easily be coded using forbidden augmented patterns involving <, *IE* and *IE*. Symmetry is coded by the forbidden pattern

$$IE(x,y) \land \overline{IE}(y,x)$$

Rule 2, above, can be imposed by forbidding the augmented pattern shown in Fig. 7. Rule 3 can be coded by the forbidden pattern:

$$(x < z) \land (y < z) \land IE(x, z) \land IE(y, z) \land IE(x, y)$$

In order to impose a bound of k on the tree-width of the constraint graph, there must exist a total variable order and relations *IE*, *IE*(x, y) (that cover all pairs of variables) such that the following augmented pattern does not occur:

$$(x\_1 < z) \land \dots \land (x\_{k+1} < z) \land IE(x\_1, z) \land \dots \land IE(x\_{k+1}, z)$$

This corresponds to a well-known characterisation of graphs with bounded treewidth as subgraphs of k-trees [22,24]. This example illustrates the fact that we need to apply a filter to the set of instances I defined by forbidding a set of augmented patterns. In this case, the filter is that I is completely specified, < is a total order on variables and *IE*, *IE* form a cover. When defining tractability of augmented patterns, we are only concerned in deciding instances satisfying the filter.

Another example which motivates the use of augmented patterns is the study of tractable languages. All known tractable constraint languages are defined by the existence of a polymorphism (a pointwise closure operation) which guarantees tractability [27]. Indeed, tractability is guaranteed by the identities satisfied by the polymorphism [4]. The existence of a polymorphism satisfying any given

**Fig. 7.** An augmented pattern.

set of identities can be stated in terms of a forbidden augmented pattern. Indeed, an augmented pattern can enforce the fact that the constraints of the instance must all have a polymorphism f and other patterns can enforce the identities that f must satisfy. By existentially quantifying over f we can then define the class of all instances whose constraints all have some majority polymorphism f, for example, or all of whose constraints have a Siggers polymorphism [39].

We illustrate this for weak near-unanimity polymorphisms, given their importance in the characterisation of tractable languages [3,41]. A binary CSP instance I has the k-ary polymorphism f : D*k* → D if for all binary relations R of I we have ∀(a1, b1),...,(a*k*, b*k*) ∈ R, (f(a1,...,a*k*), f(b1,...,b*k*)) ∈ R. The first step to expressing the fact that a binary CSP instance has the k-ary polymorphism f is to forbid the augmented pattern POLY*k*(f) shown in Fig. 8 for the case k = 4. A weak near-unanimity operation is a function f : D*k* → D satisfying the identities f(b, a, . . . , a) = f(a, b, a, . . . , a) = ... = f(a, . . . , a, b). These identities are equivalent to forbidding each of the following augmented patterns

$$\begin{aligned} (f(b, a, \dots, a) = c) \land (f(a, b, a, \dots, a) = d) \land (c \neq d) \\ (f(b, a, \dots, a) = c) \land (f(a, a, b, a, \dots, a) = d) \land (c \neq d) \\ \vdots \\ (f(b, a, \dots, a) = c) \land (f(a, \dots, a, b) = d) \land (c \neq d) \end{aligned}$$

For some fixed k, after forbidding these augmented patterns (the polymorphism pattern POLY*k*(f) as illustrated in Fig. 8 together with the above patterns corresponding to the identities of a weak near-unanimity polymorphism of arity k), we obtain a set of instances. We then have to apply a filter so that we only keep those instances I = A*I* , ρ*I* in which f is a total function and such that all domains are closed under f, i.e. for all x ∈ X and for all a1,...,a*k* ∈ D such that (x, a*i*) ∈ A*I* (i = 1,...,k), we have (x, f(a1,...,a*k*)) ∈ A*I* . This example again illustrates the fact that tractability of augmented patterns depends on the existence of a polynomial-time algorithm to decide instances satisfying the corresponding filter.

Another motivating example involves a colouring of points. Suppose that both S1 and S2 are tractable sets of flat patterns. Then we know that S1 + S2 defines the tractable class of instances in which either S1 does not occur or S2

**Fig. 8.** Polymorphisms can be defined by forbidding augmented patterns, as illustrated for this arity-4 polymorphism f.

does not occur. The number of patterns in S1+S2 is (in the worst case) quadratic in the size of S1 and S2. We can give a set of augmented patterns which is linear in the size of S1 and S2 as follows. We augment each pattern in S1 by colouring all its points red and each pattern in S2 by colouring all its points green. We then add a pattern consisting of two points, one red and the other green. The set of instances for which there is a 2-colouring of its points in which none of these augmented patterns occurs is exactly the set of instances in f(S1)∪f(S2).

#### **7 Augmented Patterns: Definitions**

An *augmented pattern* is simply a flat pattern together with a conjunction of atomic formulas such as R*i*(p1,...,p*ai* ) where each R*i* is a relation (of arity a*i*) and p1,...,p*ai* are points. An augmented pattern P occurs in another augmented pattern Q if there is a mapping from P to Q which corresponds to the occurrence of the flat version of P in the flat version of Q and which also preserves the new relation(s) R*i*. The new relation(s) R*i* may, for example, correspond to an order. As an example, the augmented pattern in Fig. 9(a) does not occur in the augmented pattern in Fig. 9(b) since the variable order is not preserved. On the other hand, the pattern P1 in Fig. 1 does occur in Fig. 9(b) since there is no variable order in P1 to preserve.

As a starting point, we can consider instances augmented with one or more new relation(s). In other words we consider structured instances (e.g. instances with an order on the variables). As usual, in order to establish a Galois connection, we have to consider the lattice of all generic instances including partiallyspecified instances (partial in the sense that certain pairs of points are joined by neither a negative nor a positive edge *or* the new relations do not form a cover, e.g. the variable order is only partial). The operations × and + and the functions f and g are defined as for sets of flat patterns. In particular, in P + Q there is no relation (e.g. no variable ordering) between the copies of P and Q in P + Q. The two lattice structures and the Galois connection between them follow from exactly the same arguments as for flat patterns.

**Fig. 9.** (a) The broken-triangle pattern (BTP). (b) An alternative pattern which defines the same class.

However, our aim is to consider the existential quantification of the relations (variable ordering, polymorphism, colouring) associated with a (set of) augmented pattern(s). As an example of an augmented pattern, consider the broken-triangle pattern (BTP) [16] shown in Fig. 9(a). We associate with this pattern all instances for which there is some variable ordering for which BTP does not occur. It turns out that, in the case of BTP, it is decidable in polynomial time whether such a variable ordering exists [16]. In general, each structured instance (e.g. an instance with new relations such as a variable ordering) has a corresponding flat version in which the new relations are forgotten, and our aim is to establish a Galois connection between sets of *flat* instances and augmented patterns.

We would like to establish a Galois connection between the set of sets of flat generic instances T and the set of sets of augmented patterns which we denote by SA. However, this does not seem possible. Instead we present in Sect. 8 a Galois connection between T and Σ*A* the set of sets of sets of augmented patterns. Each σ ∈ Σ*A* is a set of the form {S1, S2,...} where each S*i* ∈ SA is a set of patterns. Observe that since every element S of SA has a corresponding singleton element {S} in Σ*A*, we can consider Σ*A* as an extension of SA. We extend our definition of from SA to Σ*A* as follows: σ1 σ2 if ∀S2 ∈ σ2, ∃S1 ∈ σ1 such that S1 - S2. We define Σ*A* to be the set of equivalence classes with respect to the equivalence relation in Σ*A*.

We first have to understand the lattice structure of Σ*A*, ≤, where σ1 ≤ σ2 if and only if σ2 σ1. The meet and join operations of this lattice are the operations + and ∪. This follows from the following lemmas.

#### **Lemma 5.** *For* σ, σ1, σ2 ∈ Σ*A, if* σ1 σ *and* σ2 σ *then* (σ1 + σ2) σ*.*

*Proof.* Suppose that σ1 σ and σ2 σ and consider any S ∈ σ. We have ∃S*i* ∈ σ*i* such that S*i* - S (i = 1, 2). So ∀P ∈ S, ∃P*i* ∈ S*i* such that P*i* → P (i = 1, 2). Thus P1+P2 → P and hence S1+S2 - S. It follows that (σ1+σ2) σ.

**Lemma 6.** *For* σ, σ1, σ2 ∈ Σ*A, if* σ σ1 *and* σ σ2 *then* σ -(σ1 ∪ σ2)*.*

*Proof.* If σ σ1 and σ σ2, then ∀S*i* ∈ σ*i*, ∃S ∈ σ such that S - S*i* (i = 1, 2). Hence, σ -(σ1 ∪ σ2).

We fix a relational signature. Indeed, for simplicity of presentation, in the following we assume that there is a single new relation Rel of a fixed arity a (which could be the cartesian product of several relations). We denote by REL the set of all possible functions from the set of (flat) instances to the set of relations of arity a. Thus, given a flat instance I ∈ I and a function Rel ∈ REL, I, Rel(I) is an augmented version of I (e.g. the instance I with an ordering on its variables). We can now define occurrence of a set S ∈ SA of augmented patterns in an instance I ∈ I as ∀Rel ∈ REL, ∃P*A* ∈ S such that P*A* → I, Rel(I). Hence, S does not occur in I if

$$
\exists \mathcal{R} Rel \in \mathcal{R} \mathcal{E} \mathcal{L} \text{ such that } \forall P\_A \in S, \ P\_A \twoheadrightarrow \langle I, Rel(I) \rangle.
$$

Thus occurrence of a *set* S of augmented patterns depends on a single quantification over REL. This is the reason why we need to consider sets of sets of augmented patterns to obtain a Galois connection.

## **8 A Galois Connection for Augmented Patterns**

In order to establish a Galois connection between Σ*A* and T , we require the following functions F : Σ*A* → T and G : T → Σ*A*.

$$\begin{aligned} F(\sigma) &= \{ I \in \mathcal{I} \mid \forall S \in \sigma, \exists Rel \in \mathcal{R} \mathcal{E} \mathcal{L} \text{ such that } \forall P \in S, P \twoheadrightarrow \langle I, Rel(I) \rangle \} \\ G(T) &= \{ S \in \mathcal{S}\_{\mathcal{A}} \mid \forall I \in T, \exists Rel \in \mathcal{R} \mathcal{E} \mathcal{L} \text{ such that } \forall P \in S, P \twoheadrightarrow \langle I, Rel(I) \rangle \} \end{aligned}$$

To give a concrete example to illustrate the definition of F, if S contains patterns which when forbidden impose that Rel is a partial order on the variables, then F({S}) only contains instances equipped with a partial order on their variables. As in the case of BTP, we may want to impose a total order on the variables. F({S}) contains many instances which are either incompletely specified or for which Rel is not total; such instances can be recognised (and filtered out) in polynomial time and thus are irrelevant for deciding whether S is tractable or not, but are essential for the Galois connection. This is analogous to the Galois connection for flat pattern where f(S) included incompletely-specified instances.

Given a set of instances T, there may be more than one way of describing T using forbidden augmented patterns. For example, let S1 be the set of augmented patterns imposing a partial order on variables (as described in Sect. 6) together with the pattern BTP shown in Fig. 9(a), and let S2 be identical to S1 except that BTP is replaced by the pattern in Fig. 9(b). It is easy to see that F({S1}) = F({S2}). Hence, if T = F({S1}), then S1, S2 ∈ G(T).

**Theorem 6.** *The functions* F *and* G *define an antitone Galois connection between* Σ*A and* T *.*

*Proof.* To show that we have an antitone Galois connection between Σ*A* and T , it suffices to show that ∀σ ∈ Σ*A*, ∀T ∈ T , T ≤ F(σ) ⇔ σ ≤ G(T). This corresponds to (T → F(σ)) ⇔ (G(T) σ).

By definition, T → F(σ) if and only if ∀I*T* ∈ T, ∃I ∈ I with I*T* → I and such that ∀S ∈ σ, ∃Rel ∈ REL such that ∀P ∈ S, P - I, Rel(I). Thus T → F(S) if and only if ∀I*T* ∈ T, ∀S ∈ σ, ∃Rel ∈ REL such that ∀P ∈ S, P -I, Rel(I).

On the other hand, G(T) σ if and only if ∀S ∈ σ, ∃S ∈ SA with S - S and such that ∀I ∈ T, ∃Rel ∈ REL such that ∀P ∈ S , P - I, Rel(I). Thus G(T) σ if and only if ∀S ∈ σ, ∀I ∈ T, ∃Rel ∈ REL such that ∀P ∈ S, P -I, Rel(I).

We therefore have (T → F(σ)) ⇔ (G(T) σ) which completes the proof.

The Galois connection is similar to the Galois connection between T and S, as demonstrated by the following results.

**Theorem 7.** *For all* σ1, σ2 ∈ Σ*A,* F(σ1 + σ2) = F(σ1) ∪ F(σ2)*.*

*Proof.* F(σ1 +σ2) = {I ∈I|∀S ∈ σ1 +σ2, ∃Rel ∈ REL such that ∀P ∈ S, P - I, Rel(I)} = {I ∈I|∀S1 ∈ σ1, ∀S2 ∈ σ2, ∃Rel ∈ REL such that ∀P1 ∈ S1, ∀P2 ∈ S2, P1 +P2 - I, Rel(I)}. But P1 +P2 - I, Rel(I) if and only if P1 - I, Rel(I) or P2 - I, Rel(I) (by an immediate generalisation of Lemma 1 to augmented patterns). Furthermore, ∀P1 ∈ S1, ∀P2 ∈ S2, P1 - I, Rel(I) or P2 - I, Rel(I) if and only if ∀P1 ∈ S1, P1 - I, Rel(I) or ∀P2 ∈ S2, P2 - I, Rel(I). From all this, it follows that F(σ1 + σ2) = {I ∈I|∀S1 ∈ σ1, ∃Rel ∈ REL such that ∀P ∈ S1, P - I, Rel(I)} ∪ {I ∈I|∀S2 ∈ σ2, ∃Rel ∈ REL such that ∀P ∈ S2, P -I, Rel(I)} = F(σ1) ∪ F(σ2).

**Theorem 8.** *For all* σ1, σ2 ∈ Σ*A,* F(σ1 ∪ σ2) = F(σ1) ∩ F(σ2)*.*

*Proof.* F(σ1 ∪ σ2) = {I ∈I|∀S ∈ σ1 ∪ σ2, ∃Rel ∈ REL such that ∀P ∈ S, P - I, Rel(I)} = {I ∈I|∀S ∈ σ1, ∃Rel ∈ REL such that ∀P ∈ S, P - I, Rel(I)} ∩ {I ∈I|∀S ∈ σ2, ∃Rel ∈ REL such that ∀P ∈ S, P - I, Rel(I)} = F(σ1) ∩ F(σ2).

The lattice structure of Σ*A* and Theorems 7 and 8 are illustrated in Fig. 10.

**Theorem 9.** *For all* T1, T2 ∈ T *,* G(T1 ∪ T2) = G(T1) ∩ G(T2)*.*

**Fig. 10.** The function F from Σ*A* to T

*Proof.* G(T1 ∪ T2) = {S ∈ SA | ∀I ∈ T1 ∪ T2, ∃Rel ∈ REL such that ∀P ∈ S, P - I, Rel(I)} = {S ∈ SA | ∀I ∈ T1, ∃Rel ∈ REL such that ∀P ∈ S, P - I, Rel(I)} ∩ {S ∈ SA | ∀I ∈ T2, ∃Rel ∈ REL such that ∀P ∈ S, P -I, Rel(I)} = G(T1) ∩ G(T2).

**Theorem 10.** *For all* T1, T2 ∈ T *,* G(T1 × T2) = G(T1) ∪ G(T2)*.*

*Proof.* G(T1 × T2) = {S ∈ SA | ∀I ∈ T1 × T2, ∃Rel ∈ REL such that ∀P ∈ S, P - I, Rel(I)} = {S ∈ SA | ∀I1 ∈ T1, ∀I2 ∈ T2, ∃Rel ∈ REL such that ∀P ∈ S, P - I1 × I2, Rel(I1 × I2)}. Now, for any Rel ∈ REL, I1, Rel(I1) × I2, Rel(I2)→I1 × I2, Rel(I1 × I2). Thus P - I1 × I2, Rel(I1 × I2) implies P - I1, Rel(I1)×I2, Rel(I2) which (by an immediate extension of Lemma 2 to augmented patterns) is equivalent to (P - I1, Rel(I1)) ∨ (P - I2, Rel(I2)). It follows from the above that G(T1 × T2) ⊆ {S ∈ SA | ∀I1 ∈ T1, ∀I2 ∈ T2, ∃Rel ∈ REL such that (P - I1, Rel(I1)) ∨ (P - I2, Rel(I2))}. But, the latter is equal to {S ∈ SA | (∀I1 ∈ T1, ∃Rel ∈ REL such that (P - I1, Rel(I1))) ∨ (∀I1 ∈ T2, ∃Rel ∈ REL such that P - I2, Rel(I2))} = G(T1) ∪ G(T2). Thus G(T1 × T2) ⊆ G(T1) ∪ G(T2).

In order to show G(T1) ∪ G(T2) ⊆ G(T1 × T2), and hence to complete the proof, without loss of generality, we only need to show G(T1) ⊆ G(T1 × T2). Consider S ∈ G(T1). We have ∀I1 ∈ T1, ∃Rel1 ∈ REL such that ∀P ∈ S, P - I1, Rel1(I1). Therefore, for all common factors I of I1 and I2, ∃Rel ∈ REL such that ∀P ∈ S, P - I, Rel(I). Indeed, we can clearly choose Rel = Rel1 for each such I. Now I1 × I2 is the juxtaposition of copies of such common factors I. These copies are comprised of disjoint sets of points. For each such copy of a common factor I composing I1 × I2, there is a corresponding version of Rel1(I) which we denote by Rel*I* (I). The relations Rel*I* (I) are disjoint (since within I1 × I2 each common factor I is comprised of disjoint sets of points). Let R be the relation which is the union of all these Rel*I* (I). Then ∃Rel ∈ REL such that Rel(I1 × I2) = R. Now ∀P ∈ S, P - I1 × I2, Rel(I1 × I2). Therefore S ∈ G(T1 × T2) which completes the proof.

Theorems 9 and 10 are illustrated in Fig. 11.

**Fig. 11.** The function G from T to Σ*A*

In order to define tractability of sets of augmented patterns we must apply a filter to instances so that we only consider completely-specified instances with a certain property. Examples of filters include the property that an ordering relation is total or that two relations (such as the relations *IE* and *IE* that we introduced in Sect. 6) form a cover of all pairs of assignments to distinct variables. For example, in the case of BTP, we are only interested in instances equipped with a total ordering on the variables, since the pattern shown in Fig. 9(a) trivially does not occur on variables which are not ordered. This leads to the following definition of tractability.

**Definition 3.** *Let* F *be a property of instances* I ∈ I *that can be verified in polynomial time. We say that* σ ∈ Σ*A is* tractable *(with respect to the filter* F*) if there is a polynomial-time algorithm to decide the set of completely-specified instances in* F(σ) *(which satisfy the filter* F*). In particular, we say that* S ∈ S*A is tractable (w.r.t.* F*) if* {S} *is tractable (w.r.t.* F*).*

**Proposition 9.** *The tractable elements of* Σ*A form a sublattice. Furthermore, the tractable sets of augmented patterns form a join semi-lattice of* SA*.*

*Proof.* If σ1, σ2 ∈ Σ*A* are tractable, then so are σ1 +σ2 and σ1 ∪σ2. This follows immediately from the fact that F(σ1 + σ2) = F(σ2) ∪ F(σ2) and F(σ1 ∪ σ2) = F(σ2)∩F(σ2). The tractable sets of augmented patterns form a join semi-lattice, since S1, S2 tractable implies that S1 + S2 is tractable.

#### **9 Discussion and Conclusion**

In this paper we have initiated the study of the Galois connection between lattices of sets of forbidden patterns and sets of instances. The consequences of this Galois connection for expressibility and tractability questions remains largely unexplored. However, we have shown that the tractable sets of patterns form a sub-lattice.

Augmented patterns provide a rich language in which we can define many interesting classes of instances in a concise form, notably by adding an order on the variables or the values. We have seen that both bounded treewidth and the existence of a polymorphism satisfying a set of identities can be expressed using augmented patterns (together with a filter on the set of instances). This leads to an orthogonal question of the tractability of the recognition of classes defined by augmented patterns. For example, given a binary CSP instance, it is NPhard to determine whether there exists an ordering of the values under which all relations are max-closed [25]. On the other hand, it is tractable to decide whether the relations have a conservative Mal'tsev polymorphism [6]. Determining the tractability frontier of this meta-problem is an open question for augmented patterns. As we have pointed out, the recognition problem is always tractable for finite sets of flat patterns.

It is natural to ask whether the Feder-Vardi dichotomy [23] (for classes of CSP instances defined by finite languages of constraint relations) generalises to classes of CSP instances defined by augmented patterns. However, we know that no such P/NP-hard dichotomy can exist by the work on lifted patterns by Kun and Neˇsetˇril [33] and by Ladner's theorem [34]. It is an open question whether classes of CSP instances defined by forbidding *flat* patterns exhibit a dichotomy in the following sense: all finite sets of patterns are either tractable or NP-complete. We conjecture that this is true.

#### **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

## Author Index

Aleksiev, Teodor 107 Alivanistos, Dimitrios 107

Baxter, Matt 3 Bernert, Marie 17

Cochez, Michael 107 Cohen, David A. 125 Cooper, Martin C. 125

Daza, Daniel 107 Dhillon, Pyara 33

Galindo, Mauricio Javier Osorio 42

Jeavons, Peter G. 125

Kazantsev, Nikolai 93 Kishore, Beena 33

Laurier, Wim 3

Mann, Graham 33 Moreno, Luis Angel Montiel 42

Polovina, Simon 3 Priss, Uta 72

Ramparany, Fano 17 Rosing, Mark von 3

Sonea, Ovidiu-Dan 84 Stalker, Iain Duncan 93

van Bakel, Ruud 107

Živný, Stanislav 125


*3.1. Characteristics of the Surveyed Farms*

In the surveyed group of farms in Central Pomerania, nearly 38% of entities, apart from equity capital, used external sources of financing for agricultural activities, in order to improve their financial energy. Liabilities constituted on average 14.4% in the structure of financing sources of the analyzed entities. This is confirmed by the results of studies conducted so far on the high degree of self-financing of farms and their low inclination to (see e.g., [6,95]).

Table 2 presents descriptive statistics of the variables included in the analysis, on the basis of which, the characteristics of the researched farms were made.

**Table 2.** Descriptive statistics of independent variables considered in the model.

Note: No.—number of farms; Share—share of farms in total number of farms (%). Source: Own study.

The average area of a farm was 56.57 ha, with half of the studied population having an area not exceeding 38.02 ha. The minimum area of a farm was 0.88 ha, while the maximum area was 430 ha. The surveyed entities were characterized by a higher average area of agricultural land than the average area of a farm in Poland, which in 2019 amounted to 10.95 ha [96]. The most numerous group were farms with a production value between PLN 32.001 and PLN 100,000 (37.8%). Farm whose production value exceeded PLN 500,000 (6%). More than half of the population (55.2%) had a production value not exceeding PLN 100,000. Most entities were clearly focused on plant production—they constituted almost half of the surveyed group. 28.4% of the surveyed units were multi-directional farms, diversifying their production.

The surveyed farms were managed mainly by men (82.5%). The average age of the farm manager was 47 years. With regard to the level of education, it was found that farms managed by managers with secondary (37.1%) and basic vocational education (35.3%) dominated. One in five respondents declared having higher education. It was also noted that 17.5% of the surveyed farmers had economic education. Almost half of the respondents (49.1%) indicated that they have a successor who will take over the farm in the future.


*2.4. Cast Film Preparation*

The starch-glycerol and nanocomposite films were prepared by solution casting according to the method of Alves et al. [33]. Precursor solutions of the nanocomposite films with the total mass *m*total had a water content *c*aq of 97 wt %. Five different nanoparticle concentrations 0 ≤ *c*NP ≤ 9 wt % were added as well as glycerol as plasticizer with a concentration *c*gly of 30 wt %, both relative to the weighed portion of starch *m*starch. The weighed portions of chemicals were calculated according to Equation (1), considering the mass of water added *m*H2O, corrected for the water content of the other components.

$$m\_{\text{total}} = \left(1 + c\_{\text{gly}} + c\_{\text{NP}}\right) m\_{\text{starch}} + c\_{\text{aq}} m\_{\text{H}\_2\text{O}} \tag{1}$$

Starch was added to preheated water with a temperature of 70 ◦C in a water bath and stirred for 1 h to allow plastification. Glycerol and nanoparticles were then added and stirring was continued for 20 min to allow plasticization and mixing of the composite. A dry film thickness of 50 μm was targeted. Before casting in polystyrene Petri dishes (Greiner Bio-One, distributed by VWR, Ismaning, Germany), the filmogenic solutions were homogenized in an ultrasonic bath for 3 min. Excess water was evaporated from the dishes overnight in a climatic chamber (ICH 110, Memmert, Schwabach, Germany) at 40 ◦C and a relative humidity (r.h.) of 47%. The films were then peeled off from the Petri dish and turned upside down for double-sided drying overnight.

#### *2.5. Instrument Measurements*

If applicable, all measurements were performed at least in triplicate and are presented with the 95% confidence interval of the mean. The uncertainty of quantities depending on multiple variables is given by the propagation of error. For the determination of the oxygen permeability, the mean value of two measurements is given with the minimum and the maximum value.

#### 2.5.1. Particle Size and Viscosity

The hydrodynamic apparent particle size of the nanoparticle dispersions was measured by dynamic light scattering (DLS) using a Zetasizer Nano ZSP (Malvern Instruments, Worcestershire, UK). Aliquots were filtered with syringe filters with a hydrophilic PES membrane and a pore size of 1 μm (Chromafil PES, Macherey-Nagel, Düren, Germany). The harmonic intensity averaged particle diameter (*z*-average) and the polydispersity index (PdI) from the cumulants analysis were obtained for 0.025 wt % nanoparticle dispersions after equilibration for 30 min at 25 ◦C.

The volume-weighed particle size of residual microparticles was measured using a HELOS/KR laser diffraction particle size analyzer with a QUIXEL wet dispersion system (Sympatec, Clausthal-Zellerfeld, Germany) at 23 ◦C and an optical concentration of 10%. The balanced mean size *x*1*,*3 and the *span* were evaluated according to Equations (2) and (3) as

$$\mathbf{x}\_{1,3} = \int\_{x\_{\text{min}}}^{x\_{\text{max}}} \mathbf{x} q\_3(\mathbf{x}) d\mathbf{x} \text{ and } \tag{2}$$

$$spam = \frac{\mathbf{x}\_{\\$0} - \mathbf{x}\_{\\$0}}{\mathbf{x}\_{\\$0}}.\tag{3}$$

Here, *x*min and *x*max are the smallest and the largest particle size, *x* is the class midpoint and *q*3(*x*) is the volume-weighted particle size distribution. *x*10, *x*50 and *x*90 are the particle sizes corresponding to 10%, 50% and 90% of the cumulative undersize distribution, respectively.

The viscosity of the concentrated CNC dispersion was determined using a Physica MCR 501 rheometer (Anton Paar, Graz, Austria) at 25 ◦C with a cone-plate geometry. Shear flow curves were measured in the range from 0.01 to 1000 s−1.


**3.1 Viral methods for gene delivery in** *ex vivo* **gene therapy**

Viruses have evolved specialized molecular mechanisms to efficiently transport their genomes into cells. Viral vectors have developed by taking advantage of the molecular mechanisms of the virus to deliver exogenous DNA into target cells. Currently, viral vectors are frequently used molecular biology tools for delivery of genetic material into cells of a living organism (*in vivo*) or in cell culture (*in vitro*). Viral vectors are tailored to their specific applications but share a key property. Because viral vectors are essentially created from pathogenic viruses, they are modified to minimize the pathogenic properties of the original viruses. This usually involves the deletion of a portion of the viral genome that is critical for viral replication. Such viral vectors can efficiently infect cells but once the infection has taken place, they cannot replicate. The viral vectors require helper genes to provide the missing proteins for production of new virions. Replication of viral vectors is usually conducted in packaging cells that were engineered with helper genes. Therefore, viral vectors can only replicate in packaging cells and exist solely to deliver exogenous DNA to target cells where the viral vector cannot replicate.

Table 1 summarizes the types of viral vectors currently developed. In general, viral vectors are very efficient in terms of gene delivery into target cells. However, viral vectors have common problems including the following: (i) a limited DNA capacity, (ii) expression of viral genes, (iii) initiation of the antiviral immune response, (iv) reversion to a replication competent state and (v) decreasing expression over time.

Viral vectors can be classified as DNA or RNA viral vectors. DNA viral vectors are derived from viruses such as adenovirus or herpes virus, which carry their genetic material in the form of DNA. Because these viral vectors persist as an extrachromosomal element after delivery into target cells, the viral vectors remain only temporarily. One advantage of the episomal presence of the vectors is that the gene expression level is high. Because exogenous genes cannot stay indefinitely, these vectors are not suitable for *ex vivo* gene therapy. Currently, these vectors are mostly used for *in vivo* gene therapy.

Retroviral and lentiviral vectors are examples of RNA viral vectors that are replicated in target cells via reverse transcriptase to produce DNA from their RNA genomes. The DNA is then incorporated into the host's genome by an integrase. Thereafter, the virus replicates as part of the host cell's DNA, permitting long-term expression of the exogenous gene and ensuring transmission of the exogenous gene to the progeny of transduced cells. Therefore, these vectors are suitable for *ex vivo* gene therapy in which permanent gene expression is required in *in vitro* cell culture. These vectors are also widely used for *in vivo* gene therapy.

#### **3.2 Non-viral methods for gene delivery in** *ex vivo* **gene therapy**

Gene therapy was originally devised for the treatment of inherited genetic diseases, such as hemophilia and cystic fibrosis. However, the realm of gene therapy has been expanding to develop strategies for cancer, infectious diseases like HIV, and various complex diseases,

Typical efficiencies of gene delivery to primary cells are 5-10% in most current methods (Cai et al., 2002; Ding et al., 1999; Eiges et al., 2001; Lakshmipathy et al., 2004; Peister et al., 2004), which is not high enough for satisfactory *ex vivo* gene therapy. Because of this, many different methods of gene delivery have been developed using primary cells for *ex vivo* gene therapy. Generally, gene delivery methods can be divided into two categories, viral and

Viruses have evolved specialized molecular mechanisms to efficiently transport their genomes into cells. Viral vectors have developed by taking advantage of the molecular mechanisms of the virus to deliver exogenous DNA into target cells. Currently, viral vectors are frequently used molecular biology tools for delivery of genetic material into cells of a living organism (*in vivo*) or in cell culture (*in vitro*). Viral vectors are tailored to their specific applications but share a key property. Because viral vectors are essentially created from pathogenic viruses, they are modified to minimize the pathogenic properties of the original viruses. This usually involves the deletion of a portion of the viral genome that is critical for viral replication. Such viral vectors can efficiently infect cells but once the infection has taken place, they cannot replicate. The viral vectors require helper genes to provide the missing proteins for production of new virions. Replication of viral vectors is usually conducted in packaging cells that were engineered with helper genes. Therefore, viral vectors can only replicate in packaging cells and exist solely to deliver exogenous DNA to

Table 1 summarizes the types of viral vectors currently developed. In general, viral vectors are very efficient in terms of gene delivery into target cells. However, viral vectors have common problems including the following: (i) a limited DNA capacity, (ii) expression of viral genes, (iii) initiation of the antiviral immune response, (iv) reversion to a replication

Viral vectors can be classified as DNA or RNA viral vectors. DNA viral vectors are derived from viruses such as adenovirus or herpes virus, which carry their genetic material in the form of DNA. Because these viral vectors persist as an extrachromosomal element after delivery into target cells, the viral vectors remain only temporarily. One advantage of the episomal presence of the vectors is that the gene expression level is high. Because exogenous genes cannot stay indefinitely, these vectors are not suitable for *ex vivo* gene therapy.

Retroviral and lentiviral vectors are examples of RNA viral vectors that are replicated in target cells via reverse transcriptase to produce DNA from their RNA genomes. The DNA is then incorporated into the host's genome by an integrase. Thereafter, the virus replicates as part of the host cell's DNA, permitting long-term expression of the exogenous gene and ensuring transmission of the exogenous gene to the progeny of transduced cells. Therefore, these vectors are suitable for *ex vivo* gene therapy in which permanent gene expression is required in *in vitro* cell culture. These vectors are also widely used for *in vivo* gene therapy.

Gene therapy was originally devised for the treatment of inherited genetic diseases, such as hemophilia and cystic fibrosis. However, the realm of gene therapy has been expanding to develop strategies for cancer, infectious diseases like HIV, and various complex diseases,

**3.1 Viral methods for gene delivery in** *ex vivo* **gene therapy**

target cells where the viral vector cannot replicate.

competent state and (v) decreasing expression over time.

Currently, these vectors are mostly used for *in vivo* gene therapy.

**3.2 Non-viral methods for gene delivery in** *ex vivo* **gene therapy**

non-viral.

Table 1. A comparison of different viral vectors used for gene therapy

such as diabetes, dementia and hypertension. Genetic manipulations for these diseases are more complicated than genetic manipulations for the treatment of inherited genetic diseases. This means that current gene therapies need to deliver DNA, RNA, siRNA, or antisense sequences that alter gene expression within a specific cell population to manipulate cellular processes and responses. Viral vector-mediated gene deliveries are by far the most effective means of DNA delivery. However, the recombinant vector containing the therapeutic gene has to be packaged with viral coat proteins to make gene delivery possible, meaning that viral vector-mediated gene deliveries are limited to a DNA molecule of a certain size because the viral coat proteins have a limited DNA carrying capacity. Other than the physical limitation of viral vector-mediated gene deliveries, there are more limitations, such as immunotoxicity caused by viral coat proteins, restricted targeting of specific cell types, and recombination. Therefore, non-viral gene deliveries have been a very popular research topic, and many interesting and creative methods have been developed. The efficiency of gene delivery (*i.e.* transfection efficiency) is crucial to the success of non-viral gene deliveries. Various non-viral gene delivery methods currently developed could be classified into two groups: physical gene delivery methods and chemical gene delivery methods.

#### **3.2.1 Physical gene delivery methods**

Physical gene delivery methods are methods for transferring DNA molecules from the surrounding medium into cells. Naked DNA (*i.e.,* an uncomplexed form of DNA) is used in

The Mechanical Agitation Method of Gene Transfer for *Ex-Vivo* Gene Therapy 99

exogenous gene in the lipoplexes would not have a chance to be released into the cytoplasm for gene expression if the endosomes are stable. Therefore, helper lipids are added to form lipoplexes to facilitate the endosomal escape of the exogenous gene (Herringson et al., 2009a, 2009b; Savva et al., 2005). This approach is very successful because it increases the transfection efficiency dramatically. There are various combinations of cationic lipids and helper lipids available. More than 40 products are commercially available for cationic lipidbased gene delivery, including LipoTAXI (Agilent Technologies), LipofectaminTM (Invitrogen), NanoJuice® (Merck), Transfectam® (Promega), and LipoJet TM (SignaGen Laboratories). The cationic lipid-based gene delivery shows a very high transfection efficiency of up to 90 in *in vitro* cell culture. Because the cationic lipid-based lipoplexes are not stably maintained in the blood, these methods are best for *ex vivo* gene therapy. However, cationic lipid-based lipoplexes show a very poor transfection efficiency with primary cells, such as stem cells, indicating that new methodological developments are required for the practical application

Other than cationic lipids, several different positively charged materials are used as a base material for non-viral DNA delivery, such as cationic polymers (Segura & Shea, 2001), cationic peptides consisting of poly-L-Lysine (D'Haeze et al., 2007; Mullen et al., 2000; Niidome et al., 1997), or other types of cationic proteins (De Lima et al., 1999; Jean et al., 2009; Lam et al., 2004; Lee et al., 2003; Oliveira et al., 2009; Vighi et al., 2007). These approaches produce DNA carrying complexes that are more stable. However, the transfection efficiency of this method is not better than cationic lipid-based lipoplexes.

**4. Application of the mechanical agitation method to** *ex vivo* **gene therapy**

One of the main obstacles for the application of adult stem cells in *ex vivo* gene therapy is the low efficiency of gene transfer to these cells. For example, electroporation or transfection in mesenchymal stem cells yields 5-10% gene delivery efficiency (Cai et al., 2002; Ding et al., 1999; Eiges et al., 2001; Lakshmipathy et al., 2004; Peister et al., 2004). Therefore, improved gene delivery methods would potentially be very beneficial for the practical application of *ex vivo* gene therapy in patient care. In current gene transfer protocols, virus particles or lipoplexes passively diffuse through the liquid culture medium to reach their target cells, which are layered on the bottom of a culture dish (Chuck & Palsson, 1996). Because the virus particles or lipoplexes contact the target cells by passive diffusion, increasing the chance of contact between virus particles or lipoplexes and their target cells would increase the chance of gene transfer and to promote higher transfer efficiencies. One simple way to increase contact between viruses or lipoplexes and target cells is through mechanical agitation. Based on this hypothesis, we developed a mechanical agitation method for retroviral transduction of primary cells or transfection by lipoplexes (Park et al., 2009). In this method, we simply implemented a step in which virus-containing or lipoplexescontaining cell suspensions are agitated to increase the movement of viruses or lipoplexes and target cells with the purpose of generating more frequent contact between them. Suspended target cells have a better chance of making physical contact with virus particles or lipoplexes than adherent target cells because of the possibility for three-dimensional contact between the cells and viruses or lipoplexes. The simple addition of the mechanical agitation step to the conventional transduction or transfection protocol increased gene transfer efficiency two-fold above the current rates these protocols (Fig. 4). In the following

Therefore, most of these methods are designed for *in vivo* gene therapy.

of *ex vivo* gene therapy.

physical gene delivery methods. The easiest method to deliver genes into cells is to draw naked DNA into a microneedle and then inject the microneedle into cells to transfer the naked DNA directly to the cells. Though gene transfer efficiency by this method is very efficient, the method is very slow and laborious. The main drawback of this method is that microinjection can be only performed on one cell at a time, which means that this approach cannot be used for typical gene therapeutic approaches. The approach is limited to use for gene delivery into germ-line cells to produce transgenic organisms.

Currently, the most popular physical methods for gene delivery into cells are electroporation and sonoporation. The cellular membrane is punctured by an electric pulse (electroporation) (Neumann et al., 1982) or ultrasonic wave (sonoporation) (Yizhi et al., 2007). The pores in the cellular membrane are only temporarily formed, and DNA molecules pass through during the short period of time when the pores open. These methods are generally efficient and work well across a broad range of cell types. However, a high rate of cell death limits their use, especially in gene therapy. These methods are widely used for gene delivery of immortal cells in which cell viability is not a critical issue during gene transfer.

Another popular method for physical gene delivery is the use of particle bombardment. In this method, gold particles (gene gun) (Gan et al., 2000) or magnetic particles (magnetofection) (Scherer et al., 2002) are coated with naked DNA. In the gene gun method, the DNA-coated gold particles are shot into the cell using high pressure gas, and the particles pass through the cellular membrane to introduce the particles inside the cells. In the magnetofection method, a magnet is placed underneath the tissue culture dish to attract DNA-coated magnetic particles. Then, the DNA-coated magnetic particles come into contact with a cell monolayer to introduce the particles inside the cells. These methods yield reasonably high efficiency gene transfers, but do not yield better efficiencies compared to other non-viral gene transfer methods, despite the requirement for expensive equipment. Also, it is quite difficult to control the DNA entry pathway, and the metal particles in the cells following gene transfer could negatively affect cells. Therefore, these methods are not widely used.