Cécile Amblard
email: amblard@crm.umontreal.ca

Stéphane Girard
email: girard@stat.math.univ-montp2.fr

Symmetry and dependence properties within a semiparametric family of bivariate copulas

Keywords: Copulas, semiparametric family, measures of association, positive dependence, dependence orderings AMS Subject classifications: Primary 62H05, secondary 62H20

In this paper, we study a semiparametric family of bivariate copulas. The family is generated by an univariate function, determining the symmetry (radial symmetry, joint symmetry) and dependence property (quadrant dependence, total positivity, ...) of the copulas. We provide bounds on different measures of association (such as Kendall's Tau, Spearman's Rho) for this family and several choices of generating functions allowing to reach these bounds.

Introduction

The theory of copulas provides a relevant tool to build multivariate probability laws, from fixed margins and required degree of dependence. From Sklar's Theorem [START_REF] Sklar | Fonctions de répartition à n dimensions et leurs marges[END_REF], the dependence properties of a continuous multivariate distribution H can be entirely summarized, independently of its margins, by a copula, uniquely associated with H. Several families of copulas, such as Archimedean copulas [START_REF] Genest | Copules archimédiennes et familles de lois bidimensionnelles dont les marges sont données[END_REF] or copulas with polynomial sections [START_REF] Quesada-Molina | Bivariate copulas with quadratic sections[END_REF][START_REF] Nelsen | Bivariate copulas with cubic sections[END_REF] have been proposed. In [START_REF] Nelsen | Bivariate copulas with cubic sections[END_REF], the authors point out that the copulas with quadratic section proposed in [START_REF] Quesada-Molina | Bivariate copulas with quadratic sections[END_REF] can only model a weak dependence for a vector of random variables; weak in the sense that for such copulas, the Sperman's Rho and Kendall's Tau are respectively lower than 1/2 and 1/3. Then, they introduce copulas with cubic sections and conclude that copulas with higher order polynomial sections would increase the degree of dependence but simultaneously the complexity of the model. We propose to give up the polynomial form to work with a semiparametric family of copulas. The induced parametric families of copulas [START_REF] Amblard | A semiparametric family of symmetric bivariate copulas[END_REF] are generated as simply as Archimedean copulas, that is by an univariate function. Furthermore, dependence properties of copulas with polynomial sections are preserved and the degree of dependence can be increased without increasing significantly the complexity of the model. Note that, in [START_REF] Ferguson | A class of symmetric bivariate uniform copulas[END_REF], a class of symmetric bivariate copulas with a wide range of correlation coefficients is introduced, but these copulas are less convenient to perform classical calculations on probability laws than the copulas studied here. In Section 2, a specific semiparametric family is defined and its basic properties are derived. Symmetry properties are established in Section 3. Properties of three measures of association are investigated in Section 4. Section 5 is devoted to the dependence structure and the dependence ordering of the family.

Definition and basic properties

Throughout this paper, we note I = [0, 1]. A bivariate copula defined on the unit square I 2 is a bivariate cumulative distribution function with univariate uniform I margins. Equivalently, C must satisfy the following properties :

(P1) C(u, 0) = C(0, v) = 0, ∀(u, v) ∈ I 2 , (P2) C(u, 1) = u and C(1, v) = v, ∀(u, v) ∈ I 2 , (P3) ∆(u 1 , u 2 , v 1 , v 2 ) = C(u 2 , v 2 ) -C(u 2 , v 1 ) -C(u 1 , v 2 ) + C(u 1 , v 1 ) ≥ 0, ∀(u 1 , u 2 , v 1 , v 2 ) ∈ I 4 , such that u 1 ≤ u 2 and v 1 ≤ v 2 .
Let us recall that, from Sklar's Theorem, any bivariate distribution with cumulative distribution function H and marginal cumulative distribution functions F and G can be written

H(x, y) = C(F (x), G(y))
, where C is a copula. This result justifies the use of copulas for building bivariate distributions.

We consider the semiparametric family of functions defined on I 2 by :

C θ (u, v) = uv + θφ(u)φ(v), θ ∈ [-1, 1], (2.1)
where φ is a function on I. This family is a particular case of Farlie's family introduced in [START_REF] Farlie | The performance of some correlation coefficients for a general bivariate distribution[END_REF].

Let us note first that, the independent copula C 0 (u, v) = uv belongs to any parametric family {C θ } generated by a function φ. Second, the functions φ and (-φ) clearly define the same function C θ .

The following theorem, which is very similar to Theorem 2.2 in [START_REF] Quesada-Molina | Bivariate copulas with quadratic sections[END_REF], concerning bivariate copulas with quadratic sections, gives necessary and sufficient conditions on φ to ensure that C θ is a copula.

Theorem 1 φ generates a parametric family of copulas {C θ , θ ∈ [-1, 1]} if and only if it satisfies the following conditions :

(a) φ(0) = φ(1) = 0, (b) φ satisfies the Lipschitz condition : |φ(x) -φ(y)| ≤ |x -y|, ∀(x, y) ∈ I 2 .
Furthermore, C θ is absolutely continuous.

Proof: It is clear that (P1)⇔ (φ(0) = 0) and (P2)⇔ (φ(1) = 0). In the case of the C θ function, ∆ can be rewritten as

∆(u 1 , u 2 , v 1 , v 2 ) = (u 2 -u 1 )(v 2 -v 1 ) + θ(φ(u 2 ) -φ(u 1 ))(φ(v 2 ) -φ(v 1 )),
and then (b)⇒ (P3). Conversely, if there are x < y such that |φ(x) -φ(y)| > |x -y|, then with the choice θ = -1, u 1 = v 1 = x and u 2 = v 2 = y, we obtain:

∆(x, y, x, y) = (x -y) 2 -(φ(x) -φ(y)) 2 < 0.
Therefore (P3) ⇒ (b). Lastly, C θ is absolutely continuous since φ satisfies the Lipschitz condition. 2

The following corollary provides a new characterization of the functions φ generating parametric families of copulas. It will turn out to be useful in the sequel. Conversely, assume that (b) holds. Taking successively y = 0 and y = 1 in the Lipschitz condition gives (iii). 2

The function φ plays a role similar to the generating function in Archimedean copulas [START_REF] Genest | Copules archimédiennes et familles de lois bidimensionnelles dont les marges sont données[END_REF]. Each copula C θ is entirely described by the univariate function φ and the parameter θ, which tunes the dependence between the margins (see Section 4). Symmetry and dependence properties of the copula C θ will have a geometrical interpretation on the graph of φ. Furthermore, the choice of φ determines the vertical and horizontal sections of the copula up to a multiplicative factor and an additive linear function.

We now give some examples of functions φ generating parametric families of copulas. These examples will be used to illustrate the symmetry and dependence properties introduced in the following sections.

Example 1

The following functions φ generate parametric families of copulas.

1. φ [1] (x) = min(x, 1 -x) is the upper bound of Corollary 1(iii).

2. φ [2] (x) = x(1 -x) generates the Farlie-Gumbel-Morgenstern (FGM) family of copulas [START_REF] Morgenstern | Einfache Beispiele Zweidimensionaler Verteilungen[END_REF], which contains all copulas with both horizontal and vertical quadratic sections [START_REF] Quesada-Molina | Bivariate copulas with quadratic sections[END_REF].

3. φ [3] (x) = x(1 -x)(1 -2x) defines the parametric family of symmetric copulas with cubic sections proposed in [START_REF] Nelsen | Bivariate copulas with cubic sections[END_REF], equation (4.4).

4. φ [4] (x) = 1 π sin(πx) induces a family of copulas able to model strong dependence.

In the sequel, we note {C

[i]
θ } the parametric family of copulas associated to the function φ [i] , i ∈ {1, . . . , 4}. Graphs of the functions φ [i] are plotted in Figure 1. As a consequence of the condition (iii) of Corollary 1, graphs of φ [1] and (-φ [1] ) are the edges of a square K, within which lies the graph of φ.

In the following, we review several concepts of symmetry and dependence. Throughout the rest of this paper, φ denotes a function satisfying the conditions given in Theorem 1, and {C θ } represents the parametric family of copulas generated by the function φ.

Symmetry properties

Let (a, b) ∈ R 2 and (X, Y ) a random vector. We say that X is symmetric about a if the cumulative distribution function of (X -a) and (a -X) are identical. The following definitions generalize this symmetry concept to the bivariate case:

• X and Y are exchangeable if (X, Y ) and (Y, X) are identically distributed.

• (X, Y ) is marginally symmetric about (a, b) if X and Y are symmetric about a and b respectively.

• (X, Y ) is radially symmetric about (a, b) if (X -a, Y -b) and (a -X, b -Y ) follow the same joint cumulative distribution function. • (X, Y ) is jointly symmetric about (a, b) if the vectors of random variables (X -a, Y -b), (a-X, b-Y ), (X -a, b-Y ) and (a-X, Y -b) have a common joint cumulative distribution function.
The following theorem provides conditions on φ to ensure that the couple (X, Y ) with associated copula C θ is radially (or jointly) symmetric.

Theorem 2 (i) If X and Y are identically distributed then X and Y are exchangeable.

Besides, if (X, Y ) is marginally symmetric about (a, b) then:

(ii) (X, Y ) is radially symmetric about (a, b) if and only if either ∀u ∈ I, φ(u) = φ(1 -u) or ∀u ∈ I, φ(u) = -φ(1 -u). (3.1) (iii) (X, Y ) is jointly symmetric about (a, b) if and only if ∀u ∈ I, φ(u) = -φ(1 -u).
Proof:

(i) When X and Y are identically distributed, exchangeability is equivalent to the symmetry of the copula. In other words,

C θ must verify C θ (u, v) = C θ (v, u), ∀(u, v) ∈ I 2 ,
∀(u, v) ∈ I 2 , δ θ (u, v) = 0, (3.2)
where

δ θ (u, v) = C θ (u, v) -C θ (1 -u, 1 -v) -u -v + 1 = θ[φ(u)φ(v) -φ(1 -u)φ(1 -v)].
Obviously (3.1) implies (3.2). Conversely, suppose that (3.2) holds. Then,

δ 1 (u, u) = φ 2 (u) -φ 2 (1 -u) = 0 for all u ∈ I and consequently, either φ(u) = φ(1 -u) or φ(u) = -φ(1-u). If there exist (u 1 , u 2 ) such that φ(u 1 ) = φ(1-u 1 ) = 0 and φ(u 2 ) = -φ(1-u 2 ) = 0, then δ 1 (u 1 , u 2 ) = 2φ(u 1 )φ(u 2 ) = 0. As a conclusion (3.2) implies (3.1). (iii) Assume (X, Y ) is marginally symmetric about (a, b). Then (X, Y ) is jointly symmetric about (a, b) if and only if ∀(u, v) ∈ I 2 , d θ (u, v) = 0, (3.3)
where

d θ (u, v) = C θ (u, v) + C θ (u, 1 -v) -u = θφ(u)[φ(v) + φ(1 -v)]. It immediatly follows that (3.3) is equivalent to φ(u) = -φ(1 -u), ∀u ∈ I. 2
As an example, any marginally symmetric random vector (X, Y ) associated to a copula of the families

{C [i] θ }, 1 ≤ i ≤ 4
, is radially symmetric. Moreover, in the case i = 3, (X, Y ) is jointly symmetric. We now focus on the dependence properties of the semiparametric family of copulas.

Measures of association

In the next two sections, we note (X, Y ) a random vector with distribution H, assumed to have a density h, copula C and margins F and G. We consider three standard measures of association between the components of the random vector (X, Y ):

• the normalized volume between the graphs of H and F G [START_REF] Schweizer | On nonparametric measures of dependence for random variables[END_REF], [START_REF] Amblard | Estimation procedures for a semiparametric family of bivariate copulas[END_REF][START_REF] Amblard | A new bivariate extension of FGM copulas[END_REF], defined as the probability of concordance minus the probability of discordance of two vectors (X 1 , Y 1 ) and (X 2 , Y 2 ) described by the same joint bivariate law

σ = 12 1 0 1 0 |C(u, v)-uv|dudv, • Kendall's Tau
H, τ = 4 1 0 1 0 C(u, v)dC(u, v)-1, ( 4.1)
• Spearman's Rho [START_REF] Amblard | Estimation procedures for a semiparametric family of bivariate copulas[END_REF][START_REF] Amblard | A new bivariate extension of FGM copulas[END_REF], which is the probability of concordance minus the probability of discordance of two vectors (X 1 , Y 1 ) and (X 2 , Y 2 ) with respective joint cumulative law H and F G, ρ = 12

1 0 1 0 C(u, v)dudv-3.
In the case of a copula generated by (2.1), these measures can be rewritten only in terms of the function φ.

Proposition 1 Let (X, Y ) be a random vector with copula C θ given by (2.1). The coefficients of association are:

σ θ = 12|θ| 1 0 |φ(u)|du 2 , τ θ = 8θ 1 0 φ(u)du 2 , ρ θ = 12θ 1 0 φ(u)du 2 = 3 2 τ θ .
Proof: The proofs are very similar for the three coefficients. Let us consider the example of Kendall's Tau. The density

c θ (u, v) of C θ is c θ (u, v) = 1 + θφ (u)φ (v). (4.2)
Replacing in (4.1), it yields

τ θ = 4θ 1 0 φ(u)du 2 + 4θ 1 0 uφ (u)du 2 + 4θ 2 1 0 φ(u)φ (u)du 2 , = 4θ
1 0 φ(u)du 2 + 4θ φ(1) - 1 0 φ(u)du 2 + 2θ 2 [φ 2 (1) -φ 2 (0)].
Theorem 1 entails φ(1) = φ(0) = 0 and the result follows. 2

The measures τ θ and ρ θ linearly increase with θ, which appears as an association parameter. They are also proportionnals to the square of the surface lying between the graph of φ and the x-axis. Bounds for each of these measures of association are deduced from Corollary 1 (iii).

Proposition 2 ∀θ ∈ [-1, 1], 0 ≤ σ θ ≤ 3|θ|/4, |τ θ | ≤ |θ|/2 and |ρ θ | ≤ 3|θ|/4.
Therefore the range of each coefficient of association is 0 ≤ σ θ ≤ 3/4, -1/2 ≤ τ θ ≤ 1/2 and -3/4 ≤ ρ θ ≤ 3/4. The semiparametric family of copulas defined by (2.1) seems to be a good tool to build low complexity models with moderate dependences (0 ≤ |τ | ≤ 1/2). This is illustrated in Table 1 where the values obtained for the copulas presented in Example 1 are reported. Results obtained for the cubic sections copulas illustrate the fact that τ and ρ can be null although X and Y are not independent. All the values associated to {C [START_REF] Farlie | The performance of some correlation coefficients for a general bivariate distribution[END_REF] θ } are larger than those obtained with the FGM family. The bounds of Proposition 2 are obtained via the family {C [START_REF] Amblard | A semiparametric family of symmetric bivariate copulas[END_REF] θ }. This hierarchy of results graphically appears in Figure 1. For each fixed θ, the closer to the edges of the square K is the graph of φ, the larger is the coefficient of association of the copula induced by φ. Non-differentiability of φ [1] can be a drawback. In order to build more regular copulas, with measures of association closed from the upper bounds, we define the sequence of C 1 functions (φ [START_REF] Ferguson | A class of symmetric bivariate uniform copulas[END_REF] n ) as following: ∀n > 0, φ [5] n

(x) =                x if 0 ≤ x ≤ 1 2 - 1 n 1 2 1 - 1 n - n 2 x - 1 2 2 if 1 2 - 1 n < x < 1 2 + 1 n 1 -x if 1 2 + 1 n ≤ x ≤ 1.
Moreover each copula is differentiable and the associated Kendall's Tau sequence is given by τ

[5] n,θ = 8θ 1 4 - 1 3n 2 2
, n > 0.

It converges to the upper Kendall's Tau, τ [START_REF] Ferguson | A class of symmetric bivariate uniform copulas[END_REF] n,θ → θ/2 as n → ∞. It is also possible to build C ∞ copulas, such that the coefficients of association are closed from the upper bounds. Define the sequence (φ [START_REF] Genest | Copules archimédiennes et familles de lois bidimensionnelles dont les marges sont données[END_REF] n ) of C ∞ functions by: ∀n ≥ 2, φ [6] n (x) = 1 -

(x n + (1 -x) n ) 1/n .
Similarly to the previous example, for each n ≥ 2, φ [START_REF] Genest | Copules archimédiennes et familles de lois bidimensionnelles dont les marges sont données[END_REF] n induces a parametric family of copulas {C [START_REF] Genest | Copules archimédiennes et familles de lois bidimensionnelles dont les marges sont données[END_REF] n,θ }. Moreover ∀x ∈ I, φ [START_REF] Genest | Copules archimédiennes et familles de lois bidimensionnelles dont les marges sont données[END_REF] n (x) → φ [1] (x) as n → ∞ and |φ [START_REF] Genest | Copules archimédiennes et familles de lois bidimensionnelles dont les marges sont données[END_REF] n | ≤ 1. So, by Lebesgue's dominated convergence theorem, τ [START_REF] Genest | Copules archimédiennes et familles de lois bidimensionnelles dont les marges sont données[END_REF] n,θ converges to the upper bound as n → ∞. Graphs of φ [START_REF] Genest | Copules archimédiennes et familles de lois bidimensionnelles dont les marges sont données[END_REF] 2 , φ [START_REF] Genest | Copules archimédiennes et familles de lois bidimensionnelles dont les marges sont données[END_REF] 4 , and φ [START_REF] Genest | Copules archimédiennes et familles de lois bidimensionnelles dont les marges sont données[END_REF] 8 are plotted in Figure 2. We clearly see that the surface lying between the φ [START_REF] Genest | Copules archimédiennes et familles de lois bidimensionnelles dont les marges sont données[END_REF] n graph and the x-axis increases with n. The sequences (τ [START_REF] Genest | Copules archimédiennes et familles de lois bidimensionnelles dont les marges sont données[END_REF] n,1 ) and (τ [START_REF] Ferguson | A class of symmetric bivariate uniform copulas[END_REF] n,1 ) are plotted in Figure 3. We can observe that for n ≥ 2, τ [START_REF] Ferguson | A class of symmetric bivariate uniform copulas[END_REF] n,1 and τ [START_REF] Genest | Copules archimédiennes et familles de lois bidimensionnelles dont les marges sont données[END_REF] n,1 are both larger than the value obtained by the FGM copula C [START_REF] Amblard | Estimation procedures for a semiparametric family of bivariate copulas[END_REF] 1 and that they exceed the value reached by the copula C [START_REF] Farlie | The performance of some correlation coefficients for a general bivariate distribution[END_REF] 1 , whenever n ≥ 3.

Concepts of dependence

The property of independence clearly corresponds to the subset all of whose distribution members have the copula C 0 (u, v) = uv. In the same way, the dependence properties can be thought of as a subset of the set of all joint distrubutions. Many dependence properties can be described by identifying the copulas or simple properties of the copulas, which corresponds to the subset.

Positive dependence

In this subsection, we will use several concepts of positive dependence, which express that two variables are large (or small) simultaneously.

• PFD: X and Y are Positive Function Dependent if for all integrable real-valued function

g, we have E h [g(X)g(Y )] -E h [g(X)]E h [g(Y )
] ≥ 0 where E h is the expectation symbol relative to the density h.

• PQD: X and Y are Positively Quadrant Dependent if

∀(x, y) ∈ R 2 , P (X ≤ x, Y ≤ y) ≥ P (X ≤ x)P (Y ≤ y).
(5.1)

• LTD(Y |X): Y is Left Tail Decreasing in X if P (Y ≤ y|X ≤ x) is nonincreasing in x for all y.
A similar definition can be given for LT D(X|Y ). The links between these concepts [START_REF] Lehann | Some concepts of dependence[END_REF][START_REF] Nelsen | Copulas and association, Advances in probability distributions with given marginals[END_REF] are illustrated in Figure 4. The following theorem summarizes the properties of positive dependence of any vector (X, Y ) associated with the copula C θ defined by (2.1). Similar results can be established for the corresponding concepts of negative dependence.

• RTI(Y |X): Y is Right Tail Increasing in X if P (Y > y|X > x) is nondecreasing in x for all y. • SI(Y |X): Y is Stochastically Increasing in X if P (Y > y|X = x)
Theorem 3 Let θ > 0 and (X, Y ) a random vector with copula C θ .

(i) X and Y are PFD.

(ii) X and Y are PQD if and only if either ∀u ∈ I, φ(u) ≥ 0 or ∀u ∈ I, φ(u) ≤ 0.

(iii) X and Y are LTD if and only if φ(u)/u is monotone.

(iv) X and Y are RTI if and only if φ(u)/(u -1) is monotone.

(v) X and Y are LCSD if and only if they are LTD.

(vi) X and Y are RCSI if and only if they are RTI.

(vii) X and Y are SI if and only if φ is either concave or convex.

(viii) X and Y have the TP2 density property if and only if they are SI.

Proof:

(i) Let g be an integrable real-valued function on I. The density c θ of C θ is given by (4.2). Routine calculations yield

E c θ (g(X)g(Y )) -E c θ (g(X))E c θ (g(Y )) = θ 1 0 g(t)φ (t)dt 2 ≥ 0, since θ ≥ 0.
(ii) The vector (X, Y ) is PQD if and only if the uniform I-margins vector (U, V ) with distribution C θ is PQD. For (U, V ), condition (5.1) can simply be rewritten as θφ(u)φ(v) ≥ 0, ∀(u, v) ∈ I 2 and the conclusion follows.

(iii) Since C θ is symmetric, the necessary and sufficient conditions given by Theorem 5.2.5 in [START_REF] Nelsen | An introduction to copulas[END_REF], simply reduce to the unique condition: C θ (u, v)/u = v + θφ(v)φ(u)/u is nonincreasing in u for all v ∈ I. Suppose for instance φ(u)/u is nonincreasing. Then, since φ(1) = 0, we have φ(v) ≥ 0 for all v in I and thus C θ (u, v)/u is nonincreasing in u for all v ∈ I. The case of a nondecreasing function φ(u)/u is similar. Conversely, suppose C θ (u, v)/u is nonincreasing in u for all v ∈ I. If there exist v ∈ I such that φ(v) > 0 then φ(u)/u is nonincreasing too. The case where there is v ∈ I such that φ(v) < 0 is similar. The case φ(v) = 0 for all v ∈ I is trivial. Hence we have shown that C θ (u, v)/u is nonincreasing in u for all v ∈ I if and only if φ(u)/u is monotone.

(iv) Is similar to (iii).

(v) In view of Corollary 5.2.17 in [START_REF] Nelsen | An introduction to copulas[END_REF], a necessary and sufficient condition for X and Y to be LCSD is: C θ is a totally positive function of order 2. For all u 1 ≤ u 2 and v 1 ≤ v 2 , the quantity

C θ (u 1 , v 1 )C θ (u 2 , v 2 )-C θ (u 1 , v 2 )C θ (u 2 , v 1 ) = θ φ(v 2 ) v 2 - φ(v 1 ) v 1 φ(u 2 ) u 2 - φ(u 1 ) u 1 u 1 u 2 v 1 v 2
is nonnegative if and only if φ(u)/u is monotone. This is the necessary and sufficient condition for X and Y to be LTD given in (iii).

(vi) Is similar to (v).

(vii) In view of the C θ symmetry, the geometric interpretation of stochastic monotonicity given by Corollary 5.2.11 in [START_REF] Nelsen | An introduction to copulas[END_REF] provides the necessary and sufficient condition: (viii) X and Y have the TP2 density property if and only if the density of the copula satisfies

C θ (u, v)
∀u 1 ≤ u 2 , v 1 ≤ v 2 , c θ (u 1 , v 1 )c θ (u 2 , v 2 ) -c θ (u 1 , v 2 )c θ (u 2 , v 1 ) ≥ 0,
which can be rewritten as

∀u 1 ≤ u 2 , v 1 ≤ v 2 , [φ (u 1 ) -φ (u 2 )][φ (v 1 ) -φ (v 2 )] ≥ 0.
Equivalently, φ is either nonincreasing or nondecreasing which means that φ is either concave or convex. This is the necessary and sufficient condition for X and Y to be SI as established in (vii). 2

The results of Theorem 3 are illustrated in Figure 5. For instance, random vectors with copula in the parametric families generated by φ [1] , φ [2] , φ [4] , φ [START_REF] Ferguson | A class of symmetric bivariate uniform copulas[END_REF] n or φ [START_REF] Genest | Copules archimédiennes et familles de lois bidimensionnelles dont les marges sont données[END_REF] n have the TP2 density property since these functions are concave. Consequently, these random vectors are also SI, LCSD, RCSI, LTD, RTI, PQD, and PFD. When the copula belongs to the family {C [START_REF] Amblard | A new bivariate extension of FGM copulas[END_REF] θ }, the associated random vector is PFD but not PQD.

Dependence orderings

In Theorem 3 positive dependence properties of the copula C θ are established for fixed θ > 0. In this subsection we investigate how measures of dependence change as θ increases. To this end, it is necessary to define a dependence ordering which can decide whether a multivariate cumulative distribution function is more dependent than another. Consider H and H * two bivariate cumulative distribution functions with the same margins. We study two dependence orderings:

• H * is more PQD (or more concordant) than H if H(x 1 , x 2 ) ≤ H * (x 1 , x 2 ) for all (x 1 , x 2 ).
We denote H ≺ C H * this case.

• Note H 2|1 and H * 2|1 the conditional distributions of the second random variable given the first one.

H * is more SI than H if H * -1 2|1 (H 2|1 (x 2 |x 1 )|x 1 ) is increasing in x 1 . We denote H ≺ SI H * this case.
Remark that H ≺ SI H * implies H ≺ C H * (see Theorem 2.12 in [START_REF] Joe | Multivariate models and dependence concepts[END_REF]). The natural extension of these definitions to parametric families of copulas is the following.

• A family of copulas {C θ } is ordered in concordance if θ ≤ θ implies C θ ≺ C C θ . • A family of copulas {C θ } is SI ordered if θ ≤ θ implies C θ ≺ SI C θ .
As mentionned in [START_REF] Joe | Multivariate models and dependence concepts[END_REF], C θ ≺ C C θ implies τ θ ≤ τ θ and ρ θ ≤ ρ θ . We now give conditions under which the parametric family of copulas obtained by choosing φ according to Corollary 1 is stochastically ordered. Theorem 4 (i) {C θ } is ordered in concordance if and only if φ is either positive or negative.

(ii) Assume φ is twice-differentiable. {C θ } is SI ordered if φ is either convex or concave.

Proof:

(i) The proof is straigtforward.

(ii) Because of Theorem 2.14 in [START_REF] Joe | Multivariate models and dependence concepts[END_REF], {C θ } is SI ordered if for all increasing real-valued functions g,

A(u, v, θ) = ∂ 2 B ∂v∂u ∂B ∂θ - ∂ 2 B ∂θ∂u ∂B ∂v ≥ 0, where B(u, v, θ) = g(v + θφ (u)φ(v)). We obtain A(u, v, θ) = -φ (u)φ(v)[g (v + θφ (u)φ(v))] 2 .
The sign of A(u, v, θ) is given by -φ (u)φ(v), which is positive whenever φ is concave or convex.

For instance, all families discussed in this document are ordered in concordance, but {C [START_REF] Amblard | A new bivariate extension of FGM copulas[END_REF] θ } is not SI ordered.

Conclusion

In this paper, a symmetric semiparametric family of copulas is studied and its symmetry and dependence properties are established. As for Archimedean copulas, a parametric subfamily is generated by a univariate function and both symmetry and dependence properties of the family can be geometrically interpreted on the graph of the generating function. Furthermore, the horizontal and vertical sections of the copula are essentially described by the generating function. Finally, the proposed family of copulas provides a simple way to model moderate degrees of dependence. Extension to higher levels of dependence is considered in [START_REF] Amblard | A new bivariate extension of FGM copulas[END_REF]. Future work will consist of generalizing the family definition to the multivariate case (dimension of the random vector upper than 2). We also refer to [START_REF] Amblard | Estimation procedures for a semiparametric family of bivariate copulas[END_REF] for estimation techniques dedicated to this family of copulas. x(1-x) x(1-x)(1-2x) sin(pi x)/pi min(x,1-x) -min(x,1-x) 1 , circles: τ [START_REF] Ferguson | A class of symmetric bivariate uniform copulas[END_REF] n,1 and crosses: τ φ(x) σ θ τ θ ρ θ φ [1] (x) = min(x, 1 -x) 3|θ|/4 θ/2 3θ/4 φ [2] (x) = x(1 -x) |θ|/3 2θ/9 θ/3 φ [3] (x) = x(1 -x)(1 -2x) 3|θ|/64 0 0 φ [4] (x) = 1 π sin (πx) 48|θ|/π 4 32θ/π 4 48θ/π 4

  is a concave function of u. Suppose φ is a concave function. Then, taking into account that φ(0) = φ(1) = 1, we easily show that φ(v) ≥ 0 for all v ∈ I and therefore C θ (u, v) is a concave function of u. The case of a convex function φ is similar. Conversely, suppose C θ (u, v) is a concave function of u. If there exists a v such that φ(v) > 0 then (2.1) shows that φ is concave. The case where there exists a v ∈ I such that φ(v) < 0 is similar. The case φ(v) = 0 for all v ∈ I is trivial. Hence we have shown the equivalence between C θ (u, v) is a concave function of u and φ is concave or convex.

Figure 1 :

 1 Figure 1: Graphs of the functions φ [i] , i ∈ {1, . . . , 4} presented Example 1.

Figure 3 :

 3 Figure 3: Comparison of several Kendall's Tau sequences. Solid line: τ [2]1 , dashed line: τ[START_REF] Farlie | The performance of some correlation coefficients for a general bivariate distribution[END_REF]

Figure 4 :Figure 5 :

 45 Figure 4: Implications among dependence properties in the general case.

  is nondecreasing in x for all y. • LCSD: X and Y are Left Corner Set Decreasing if P (X ≤ x, Y ≤ y|X ≤ x , Y ≤ y ) is nonincreasing in x and y for all x and y. • RCSI: X and Y are Right Corner Set Increasing if P (X > x, Y > y|X > x , Y > y ) is nondecreasing in x and y for all x and y. • TP2 density: (X, Y ) have the TP2 density property if h is a totally positive function of order 2 i.e. h(x 1 , y 1 )h(x 2 , y 2 ) -h(x 1 , y 2 )h(x 2 , y 1 ) ≥ 0 for all (x 1 , x 2 , y 1 , y 2 ) ∈ I 4 such that x 1 ≤ x 2 and y 1 ≤ y 2 . When X and Y are exchangeable, Y is Stochastically Increasing in X if and only if X is Stochastically Increasing in Y . Will will denote this property SI. Similarly, we will denote LTD the equivalent properties LTD(Y |X) and LTD(X|Y ), and RTI, RTI(Y |X) or RTI(X|Y ).

Table 1 :

 1 Measures of dependence associated to the Example 1 copulas.

Acknowledgements

This work has been done while the second author was visiting the Centre de Recherche Mathématiques in the Université de Montréal. The center's hospitality is gratefully acknowledged.


Sonia Duprey
email: sonia.duprey@univ-lyon1.fr

Laurence Cheze

Raphaël Dumas

Influence of joint constraints on lower limb kinematics estimation from skin markers using global optimization

In order to obtain the lower limb kinematics from skin-based markers, the soft tissue artefact (STA) has to be compensated. Global optimization (GO) methods rely on a predefined kinematic model and attempt to limit STA by minimizing the differences between model predicted and skin-based marker positions. Thus, the reliability of GO methods depends directly on the chosen model, whose influence is not well known yet.

This study develops a GO method that allows to easily implement different sets of joint constraints in order to assess their influence on the lower limb kinematics during gait. The segment definition was based on generalized coordinates giving only linear or quadratic joint constraints. Seven sets of joint constraints were assessed, corresponding to different kinematic models at the ankle, knee and hip: SSS, USS, PSS, SHS, SPS, UHS and PPS (where S, U and H stand for spherical, universal and hinge joint and P for parallel mechanism). GO was applied to gait data from five healthy males.

Results showed that the lower limb kinematics, except hip kinematics, knee and ankle flexion-extension, significantly depend on the chosen ankle and knee constraints. The knee parallel mechanism generated some typical knee rotation patterns previously observed in lower limb kinematic studies. Furthermore, only the parallel mechanisms produced joint displacements.

Thus, GO using parallel mechanism seems promising. It also offers some perspectives of subject-specific joint constraints.

These constraints represent the femur/tibia sphere-on-plane medial and lateral contacts (sphere centres 1 3 V , 2 3 V and radii 1 K d , 2 K d , contact plane points 6 2 V , 7 2 V and normals 3 2 n , 4 2 n ) and the anterior cruciate, posterior cruciate and medial collateral ligaments (origins 3 3 V ,

Introduction

To obtain an accurate skeleton kinematics from skin-based markers, the relative motion of soft tissues with regards to the underlying bone (i.e. the soft tissue artefact, STA) has to be compensated. Several methods minimizing STA have been developed [START_REF] Leardini | Human movement analysis using stereophotogrammetry. Part 3: Soft tissue artifact assessment and compensation[END_REF]. Some methods address each segment separately by computing the optimal bone pose from a marker cluster [START_REF] Söderkvist | Determining the movements of the skeleton using wellconfigured markers[END_REF][START_REF] Challis | A procedure for determining rigid body transformation parameters[END_REF][START_REF] Cheze | A solidification procedure to facilitate kinematic analyses based on videa system data[END_REF], while global optimization (GO) methods address the entire limb, or full body, by minimizing distances between measured and model-determined marker positions [START_REF] Lu | Bone position estimation from skin marker co-ordinates using global optimisation with joint constraints[END_REF]. GO methods rely on the determination of a predefined kinematic model with specific joint constraints. Therefore, GO results directly depend on the constraint choices.

Spherical joints have been classically applied [START_REF] Lu | Bone position estimation from skin marker co-ordinates using global optimisation with joint constraints[END_REF][START_REF] Charlton | Repeatability of an optimised lower body model[END_REF].

Alternatively, models including universal and hinge joints at the ankle and knee were proposed [START_REF] Reinbolt | Determination of patient-specific multi-joint kinematic models through two-level optimization[END_REF]Andersen et al., 2009c). Moreover, degree-of-freedom coupling curves were included as knee joint constraints in a registration technique [START_REF] Sholukha | Double-step registration of in vivo stereophotogrammetry with both in vitro 6-DOFs electrogoniometry and CT medical imaging[END_REF] providing reliable results in terms of joint displacements. However the coupling curves were dependent on the chosen segment axes and Euler angle sequence.

Coupled degrees-of-freedom can also be modelled by spatial parallel mechanisms [START_REF] Feikes | A constraint-based approach to modelling the mobility of the human knee joint[END_REF][START_REF] Gregorio | Mathematical models of passive motion at the human ankle joint by equivalent spatial parallel mechanisms[END_REF] that directly take into account anatomical structures (i.e. articular surfaces as sphere-on-plane contacts and ligaments as constant lengths). The corresponding joint constraints have not been included in GO methods so far.

The aim of the current study is to develop a GO method that allows to easily implement different sets of joint constraints, in order to assess their influence on the lower limb kinematics during gait. Different sets of joint constraints were evaluated, corresponding to different kinematic models at the ankle, knee and hip joints: SSS, USS, PSS, SHS, SPS, UHS and PPS (where S, U and H stand for spherical, universal and hinge joint and P for parallel mechanism).

Global optimization methods (see appendices A, B, C for more details)

Parameter set GO was performed using generalized coordinates [START_REF] Dumas | 3D inverse dynamics in non-orthonormal segment coordinate system[END_REF] consisting, for each segment i, of two position vectors (the proximal P i and distal D i endpoints) and two unitary direction vectors (u i and w i ):

i i T i i P D i   =   Q u r r w (1)
with i = 1, 2, 3, 4 for the foot, shank, thigh, and pelvis, respectively.

These parameters were designed to stand for non-orthogonal directions: inertial (for inverse dynamics purpose), anatomical (i.e., from joint centre to joint centre) and functional (i.e., mean axis of rotation). Particularly, r D2 and r P2 are the ankle and knee joint centres while w 2 and w 3 are the ankle and knee flexion-extension axes. In addition, any position r of a point (marker or virtual) and any direction n embedded in the segment i can be straightforwardly deduced from Q i through a constant interpolation matrix N i (Garcia de [START_REF] Garcia De Jalon | Natural coordinates for the computer analysis of multibody systems[END_REF][START_REF] Dumas | 3D inverse dynamics in non-orthonormal segment coordinate system[END_REF]. As 12 parameters represent the 6 degrees of freedom of the segment, rigid body constraints have to be considered in addition to the joint constraints.

Objective function

The objective function to minimize is the sum of the square distances between measured and model-determined marker positions:

2 4 1 1 ) ( i M i i m j M j i i j i f Q N r - = ∑∑ = = (2)
with j i M the j th marker (out of m i ) embedded in segment i, j i M r its measured position and

j i M i

N

the corresponding interpolation matrix.

Joint constraints

For the spherical model, the joint constraints at the ankle, knee and hip are: For the universal joint at the ankle, the joint constraints are: For the hinge model at the knee, the joint constraints are:

2 1 1 1 2 1 1 0 cos 0 D P A θ -=    • - =   n r r w N Q , ( 4
( ) For the parallel mechanism at the ankle (Di [START_REF] Gregorio | Mathematical models of passive motion at the human ankle joint by equivalent spatial parallel mechanisms[END_REF], the joint constraints are:

3 2 2 2 1 3 2 2 3 2 0 cos 0 cos 0 D P P D K K L θ θ -=    • - - =   • - =  
( ) ( ) ( ) ( ) ( ) ( ) ( )            = - • - = - - = - - = - • - = - • - 0 0 0 0 0 5 1 1 1 1 2 2 2 4 2 1 1 2 2 2 3 2 1 1 2 2 2 2 2 2 2 1 1 1 2 2 2 2 1 1 2 1 5 1 5 2 4 1 4 2 3 1 3 2 2 2 2 2 2 1 1 2 1 2 1 1 A V V A V V A V V A V V A V V d d d d d Q N Q N Q N Q N Q N Q N Q N Q N Q N Q N Q N Q N Q N n n n , (6)
These constraints represent the tibia/talus sphere-on-plane medial and lateral contacts (sphere For the parallel mechanism at the knee [START_REF] Feikes | A constraint-based approach to modelling the mobility of the human knee joint[END_REF], the joint constraints are:

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 6 3 3 2 2 2 7 4 3 2 2 3 8 3 2 4 9 3 2 5 10 3 2 1 3 3 2 2 2 2 2 3 3 2 2 2 2 2 2 3 3 3 2 2 2 2 4 3 3 2 2 2 2 5 3 3 2 2 0 0 0 0 0 V V K V V K V V K V V K V V K d d d d d  - • - =   - • - =    - - =    - - =   - - =   n n N Q N Q N Q N Q N Q N Q N Q N Q N Q N Q N Q N Q , ( 7
)

Model construction and initial guess

The construction of the lower limb kinematic models corresponds to the determination of the constants (i.e. interpolation matrices N, angles θ, lengths L and distances d) from static calibration, functional methods and literature data (Di [START_REF] Gregorio | Mathematical models of passive motion at the human ankle joint by equivalent spatial parallel mechanisms[END_REF][START_REF] Feikes | A constraint-based approach to modelling the mobility of the human knee joint[END_REF].

In the optimization process, the initial values of the parameters are obtained by constructing at each frame the position vectors r Pi and r Di and direction vectors u i and w i from the skin-based markers [START_REF] Dumas | 3D inverse dynamics in non-orthonormal segment coordinate system[END_REF]; see also Appendix A).

Application

Five healthy male subjects (age: 28.8±4.8 years; height: 1.74±0.09 m; mass: 76.5±13.5 kg)

participated in this study. The trajectories of 32 skin-based markers on the right lower limb were recorded at 100 Hz. The parameters Q i were obtained by minimization of the objective function f under constraints (i.e., rigid body and different sets of kinematic constraints) with the use of the « fmincon » Matlab function (Mathworks, USA). Then, the classical segment coordinate systems were deduced from the Q i parameters [START_REF] Dumas | 3D inverse dynamics in non-orthonormal segment coordinate system[END_REF] and the joint angles and displacements were computed [START_REF] Wu | ISB recommendation on definitions of joint coordinate system of various joints for the reporting of human joint motion-part I: ankle, hip, and spine[END_REF]; see also Appendix C). RMS differences were computed for each curve and averaged for the 5 subjects.

Results

Constraint influence

The hip kinematics was not much affected by ankle and knee constraint variations (Fig. 1, Table 1): all models provided similar patterns and amplitudes for the hip flexion-extension and abduction-adduction, and the dispersion of the internal-external rotations remained low.

The knee flexion-extension curves did not vary across models: a single pattern could be observed and the dispersion was low. The patterns of the abduction-adduction, internalexternal rotation and displacement curves appeared to depend on the applied knee constraint (Fig. 2), but not on the ankle constraint. However, ankle constraints caused a dispersion of the internal-external rotations (Table 1).

The ankle flexion-extension curves showed a similar pattern for all models with a slight dispersion (Fig. 3). The ankle abduction-adduction, internal-external rotation and displacement curves varied whenever the ankle or knee constraint was modified (Tables 1 and2), except for the PPS and PSS models which provided similar rotation patterns and, for some subjects, similar displacement patterns.

Comparison with in-vivo (intra-cortical pins) data from the literature

The hip kinematics reproduced typical patterns (the authors were not aware of any hip in-vivo data).

The knee flexion-extension biphasic pattern [START_REF] Lafortune | Three-dimensional kinematics of the human knee during walking[END_REF][START_REF] Benoit | Effect of skin movement artifact on knee kinematics during gait and cutting motions measured in vivo[END_REF] amplitude and internal rotation occurring twice during the stance phase (at heel strike and toeoff) was found when the model included a knee parallel mechanism. Furthermore, only the knee parallel mechanism could reproduce the femoral rollback.

The ankle flexion-extension curves reproduced the typical 2-peak pattern [START_REF] Reinschmidt | Three-dimensional tibiocalcaneal and tibiofemoral kinematics during human locomotion -measured with external and bone markers[END_REF][START_REF] Reinschmidt | Tibiocalcaneal motion during running, measured with external and bone markers[END_REF]. All models roughly produced an initial abduction followed by a slight adduction during stance and internal-external rotations of limited amplitude, as observed in in-vivo studies [START_REF] Reinschmidt | Three-dimensional tibiocalcaneal and tibiofemoral kinematics during human locomotion -measured with external and bone markers[END_REF][START_REF] Reinschmidt | Tibiocalcaneal motion during running, measured with external and bone markers[END_REF]. Besides, only the parallel mechanisms produced joint displacements.

Discussion and conclusions

GO with joint constraints is one of the methods developed for minimizing STA. Its reliability is under controversy [START_REF] Stagni | Double calibration vs. Global optimisation: Performance and effectiveness for clinical application[END_REF]Andersen et al., 2009a). Nevertheless, defining a kinematic model is becoming usual in gait analysis (e.g., inverse-forward dynamics, musculoskeletal models) and the constraint choice is essential.

In this study, a GO method was developed to implement different sets of joint constraints.

The segment definition, based on generalized coordinates [START_REF] Dumas | 3D inverse dynamics in non-orthonormal segment coordinate system[END_REF], allowed to readily implement complex constraints. Besides, the classical segment and joint coordinate systems could easily be deduced.

Results showed that the lower limb kinematics, except hip kinematics, knee and ankle flexion-extension, significantly depend on the chosen set of constraints. An appropriate choice, such as the parallel mechanisms, seemed to provide physiologic patterns (i.e., limited abduction-adduction at the knee and femoral rollback). Furthermore, these mechanisms offer the possibility of matching model geometry with MRI data (e.g., by customizing the femur condyles centre and radius) and of adapting the model to pathologies (e.g., by suppressing a ligament constraint). Thus, these mechanisms might be able to provide efficient subjectspecific models for clinical applications.

A major limitation of this study is the lack of in-vivo data. The ability to reproduce intersubject variability, which is an important criterion in the constraint choice, could not be assessed and subject-by-subject validation could not be performed. Thus, further studies enabling subject-by-subject comparisons would offer interesting perspectives.

  point (i.e., hip joint centre) embedded in the pelvis segment and

  ) with θ A the angle defining the relative orientation of the two functional joint axes,

θ

  two angles defining the orientation of the joint axes and L 2 the shank segment length.


Therese Biedl
email: biedl@uwaterloo.ca

Michal Stern
email: stern@mta.ac.il

David R Cheriton

On edge-intersection graphs of k-bend paths in grids

Keywords: Intersection graphs, planar graphs, graph drawing

Edge-intersection graphs of paths in grids are graphs that can be represented such that vertices are paths in a grid and edges between vertices of the graph exist whenever two grid paths share a grid edge. This type of graphs is motivated by applications in conflict resolution of paths in grid networks.

In this paper, we continue the study of edge-intersection graphs of paths in a grid, which was initiated by Golumbic, Lipshteyn and Stern. We show that for any k, if the number of bends in each path is restricted to be at most k, then not all graphs can be represented. Then we study some graph classes that can be represented with k-bend paths, for small k.

We show that every planar graph has a representation with 5-bend paths, every outerplanar graph has a representation with 3-bend paths, and every planar bipartite graph has a representation with 2-bend paths. We also study line graphs, graphs of bounded pathwidth, and graphs with κ-regular edge orientations.

Introduction

Presume you have a network and need to route calls in it. Since calls interfere with each other, you need to route calls such that no two connections share a link. This transforms into a colouring problem in an edge-intersection graph of paths. The network is the host graph, and each call becomes a path in the host graph; calls share a link if and only if the paths share an edge of the host graph. The edge-intersection graph defined by this has a vertex for every path, and vertices are adjacent if and only if the paths have overlapping edges; the goal is hence to colour this edge-intersection graph.

Edge-intersection graphs of paths in a network have been studied almost exclusively for networks that are trees; this graph class is known as EPT graphs and was introduced over 20 years ago, though research is still ongoing (see [START_REF] Golumbic | The k-edge intersection graphs of paths in a tree[END_REF] and the references therein).

Very recently, Golumbic, Lipshteyn and Stern generalized the framework by allowing networks that are grids, rather than trees [START_REF] Golumbic | Edge intersection graphs of single bend paths on a grid[END_REF]. Thus, they define EPG graphs to be the edge-intersection graphs of paths in a grid. They showed that every graph is an EPG graph, and then restricted the graph class by limiting the number of bends for the paths, i.e., the number of times that the direction of the path switches from horizontal to vertical. (See [START_REF] Golumbic | Edge intersection graphs of single bend paths on a grid[END_REF] for more motivation of why few bends are relevant for chip manufacturing.) Focusing on the case of single bends, they proved a number of existence and impossibility results.

In this paper, we continue this work, and study graphs that can be represented with few (but more than 1) bends in each path. We first show that for any given k, there exist graphs that are not k-bend EPG graphs. We then study planar graphs and subclasses thereof, and give upper and lower bounds on the number of bends required for planar graphs, outerplanar graphs and planar bipartite graphs. We also study some other graph classes, such as line graphs, graphs of bounded pathwidth, and graphs that have edge orientations with bounded indegrees.

Related results

EPG graphs have, to our knowledge, not been studied except by Golumbic, Lipshteyn and Stern [START_REF] Golumbic | Edge intersection graphs of single bend paths on a grid[END_REF] and the very recent work by Asinowski and Suk [START_REF] Asinowski | Edge intersection graphs of systems of grid paths with bounded number of bends[END_REF]. The closest related works are on representing graphs by paths with other restrictions. Much is known about representing graphs as intersection graphs of paths in trees, not grids, both for vertex-intersection and edge-intersection. These are the so-called VPT graphs and EPT graphs (see for example [START_REF] Golumbic | The k-edge intersection graphs of paths in a tree[END_REF][START_REF] Monma | Intersection graphs of paths in a tree[END_REF] and the references therein).

Another related line of work does not put any restrictions on the paths (i.e., they are arbitrary Jordan curves in the plane): these are the string graphs. Kratochvíl proved that recognizing them is NP-hard [START_REF] Kratochvil | String graphs ii: Recognizing string graphs is NP-hard[END_REF], but only recently was it proved that recognizing them is in NP [START_REF] Schaefer | Recognizing string graphs is in NP[END_REF]. Restricting Jordan curves further to intersect each other at most once gives the class of 1-STRING graphs; it was shown only recently that this includes the planar graphs [START_REF] Chalopin | Planar graphs are in 1-string[END_REF] and all chordal VPT graphs [START_REF] Dangelmayr | Chordal graphs as intersection graphs of pseudosegments[END_REF].

Definitions

We assume familiarity with graph theory notation, see for example Golumbic's book [START_REF] Golumbic | Algorithmic graph theory and perfect graphs[END_REF]. In this paper, grid is used to denote the 2-way infinite orthogonal grid, i.e., the vertices are all points in 2D with integer coordinates, and grid points are adjacent if they have distance 1. A (grid) path is a path in the grid. A bend is a place where a grid path changes direction. A (grid) segment is a grid path without any bends. Two grid paths (edge-)intersect if they share at least one grid edge, otherwise they are (edge-)disjoint. Note that edge-disjoint grid paths may still share a vertex of the grid. As we will never consider any other kind of intersection, we omit 'edge-' from now on. We will also omit "grid" whenever this does not lead to confusion.

An EPG representation of a graph G = (V, E) is an assignment of grid paths to vertices of G such that (v, w) is an edge if and only if the paths assigned to v and w intersect. We call it a k-bend EPG representation if every grid path representing a vertex has at most k bends. A graph is called a k-bend EPG graph if it has a k-bend EPG representation. (These graphs were called B k -EPG graphs in [START_REF] Golumbic | Edge intersection graphs of single bend paths on a grid[END_REF].) In what follows, we often identify the graph-theoretic concept (such as vertex) with the geometric object that represents it (the grid path).

An EPG representation is said to have grid-size w × h if there are w columns and h rows that contain a bend or endpoint of a grid path representing a vertex.

k-bend EPG graphs

In this section, we will show that the complete bipartite graph K (k+3)/2,N is not a k-bend EPG graph, for some N ∈ O(k 4 ). As we learned only recently, a similar result, without asymptotic bounds on N , was discovered independently [START_REF] Asinowski | Edge intersection graphs of systems of grid paths with bounded number of bends[END_REF]. We note here that the fact that some graphs are not k-bend EPG graphs could be proved quite easily, using K N,N for large enough N . We work here on keeping one side of the ccmplete bipartite graph small so that it can be used for lower bounds for planar graphs later on.

Theorem 1 K (k+3)/2,N is not a k-bend EPG graph for some N ∈ O(k 4 ).

Proof: Set = (k + 3)/2 and N = 2 (k+1) 2 + 1 ∈ O(k 4 ). Let V = A ∪ B be the vertex partition of K ,N , with |B| = N . Assume for contradiction that K ,N has a k-bend EPG representation, and let S be the grid segments of the paths representing vertices in A; S contains at most (k + 1) many segments.

Every path representing a vertex in B must intersect of the segments in S, and no two of these paths can intersect such segments at the same place since the vertices in B are an independent set. Consider two segments s 1 and s 2 in S, and assume that P is a path that intersects both and has at most one bend inbetween. If s 1 and s 2 have the same orientation (horizontal or vertical), then P cannot have a bend inbetween them, and hence must contain an endpoint of each of s 1 and s 2 . If s 1 and s 2 have different orientation, then P must contain a bend between them, and it necessarily must be on the point where the two lines through s 1 and s 2 intersect. So in the first case there can be at most one, and in the second case at most two edge-disjoint paths that go from s 1 to s 2 with at most one bend inbetween.

Considering now all (k+1) 2 possible pairs of grid segments. So at most 2 (k+1) 2 grid paths can contain two of them consecutively with at most one bend inbetween. By choice of N , there is at least one vertex in B for which the representing path hence contains at least two bends between any two intersections with grid segments in S. Since the path intersects grid segments, it has at least 2 -2 = k+1 bends total, a contradiction. 2

We conjecture that the value of N in the above theorem is too large, and that already K ,N , for some ∈ θ(k) and N ∈ θ(k 2 ) is not a k-bend EPG graph. The graph to provide the lower bound is a bipartite graph. Hence we now study how many bends are needed in an EPG representations for bipartite graphs. Proof: Fig. 1 illustrates the construction for the complete bipartite graph K a,b . (Our construction is essentially the same as the one by Golumbic et al. [START_REF] Golumbic | Edge intersection graphs of single bend paths on a grid[END_REF], except that one bend can be saved since the graph is bipartite.) Represent each of the a vertices as a horizontal line, say at y-coordinates 1, 2, . . . , a. Define a "vertical zig-zag" to be the path

(1, 1) -(2, 1) -(2, 2) -(1, 2) -. . . -(1, 2i -1) -(2, 2i - 1) -(2, 2i) -(1, 2i) -. . . that ends with horizontal segment (1, b) -(2, b) or (2, b) -(1, b).
Represent each of the b vertices by such a zig-zag, translated horizontally as to make them vertex-disjoint. (For the complete bipartite graph, they could in fact be placed even closer so that they share vertices; this would reduce the width to |B|+1.) One easily verifies that this is an EPG representation of K a,b with the desired properties. For an arbitrary bipartite graph, we can obtain an EPG representation similarly, by omitting a "zig" or "zag" at any pair of vertices where no edge exists.

2

Notice in particular that K (k+3)/2,N is not a k-bend EPG graph for sufficiently large N by Theorem 1, but it is a (k + 1)-bend EPG graph by Theorem 2. So for any odd k, there exists a graph that is a (k + 1)bend EPG graph, but not a k-bend EPG graph, which proves that the set of k-bend EPG graphs forms a non-collapsing hierarchy. (It remains open whether the above statement also holds for even k; we suspect that this is the case.) Furthermore, Theorem 1 shows that the bound on the number of bends in Theorem 2 is tight if |B| is large (but can be improved if |B| is small [START_REF] Asinowski | Edge intersection graphs of systems of grid paths with bounded number of bends[END_REF]).

Planar graphs

A planar graph is a graph that can be drawn without crossing in the 2-dimensional plane. Much is known about planar graphs (see e.g. [START_REF] Nishizeki | Planar Graphs: Theory and Algorithms[END_REF]). We will study here bounds on the number of bends needed in EPG representations, both for planar graphs and for some of their subclasses.

Planar graphs are 5-bend EPG graphs

We show that every planar graph has a 5-bend EPG representation. Moreover, the layout of the paths for this is such that the paths only touch; they do not cross (in some sense, this is therefore a planar drawing.)

We construct this representation using the canonical ordering for triangulated planar graphs. We explain the approach and these terms in detail in the following:

• First, fix an arbitrary planar drawing Γ of the graph. This fixes the planar embedding (the clockwise order of edges around each vertex), the faces (the maximal connected regions of R 2 -Γ) and the outer-face (the face which is unbounded.)

• Add edges to the graph to make it triangulated, i.e., it is planar and every face is a triangle. It is well-known that this can always be done.

• For triangulated planar graphs, there exists the canonical ordering introduced by de Fraysseix, Pach and Pollack [START_REF] De Fraysseix | How to draw a planar graph on a grid[END_REF]. This is a vertex order v 1 , . . . , v n such that {v 1 , v 2 , v n } is the outer-face, and for all i ≥ 3, v i is a vertex in the outer-face of the graph G i-1 induced by v 1 , . . . , v i-1 , and incident to a consecutive set of at least two vertices on the outer-face of G i-1 . See also Figure 2.

The canonical ordering can be used to obtain many types of graph drawings for planar graphs, e.g., straight-line drawings, orthogonal drawings, visibility representations, and others (see e.g. [START_REF] Kant | Drawing planar graphs using the canonical ordering[END_REF]). These drawings are usually obtained by maintaining some invariant on the drawing while adding vertices according to the ordering. We do the same for obtaining an EPG representation with up to 5 bends per grid path.

Theorem 3 Every planar graph has a 5-bend EPG representation in an (n -1) × (2n -3)-grid.

Proof: We show this first for trianglated graphs. Compute a canonical ordering. To create the EPG representation, we start with v 1 and v 2 as illustrated in Fig. 2. While adding more vertices, we maintain the invariant that any vertex on the outer-face is represented by a grid path with at most 4 bends that ends in an upward ray that does not intersect any other grid path. Moreover, the order of these unobstructed rays from left to right is the same as the clockwise order of the corresponding vertices on the outer-face, starting at v 1 and ending at v 2 . Clearly the invariant holds initially.

Vertex v i can then be added by placing it between the upward rays of its leftmost earlier neighbour c α (i.e., the neighbour in G i-1 that comes first in clockwise order around the outer-face) and the rightmost earlier neighbour c β (defined similarly.) See Figure 2. The path for v i shares one vertical grid-edge with c α along the ray of c α , continues horizontally to the ray of c β , shares one grid-edge with it, then U-turns and turns again to end in an upward ray as desired. (If the rays of c α and c β are in consecutive columns, then we insert (i) a new column between them for v i .) All this is done in two rows that are above all previously used rows. For any earlier neighbour v h = c α , c β of v i , the path of v h ends in a ray between the rays of c α and c β by the invariant. We let the grid-path of v h turn to share one horizontal grid-edge with v i . Thus v h now has at most 5 bends and does not end in a ray anymore, which is compatible with the invariant since v h is not on the outer-face after adding v i .

Repeating this until i = n gives an EPG representation of the triangulated graph. The bound on the size is easily proved since every vertex adds two rows and at most 1 column, except for v 1 and v 2 (which use 1 row and 2 columns total) and v n (which does not add a column since it has at least 3 earlier neighbours.)

For graphs that are not triangulated, make them triangulated by adding edges. Draw the resulting graph G as above, but modify the construction for v i slightly for any added edge (v h , v i ) with h < i. If v h is the leftmost earlier neighbour, omit the first segment of v i . If v h is neither leftmost nor rightmost earlier neighbour, omit the last segment of v h . If v h is the rightmost earlier neighbour, then re-route the path of v i to turn upward into the ray immediately, without visiting the ray of v h . In any of these cases, the grid paths of v h and v i now have no more edges in common, and hence we have an EPG representation of the original graph with the same bounds on the size and bends.

2

v 1 v 2 v 1 v 2 v i v i leftmost predecessor rightmost predecessor c α c β c α c β EPG representation of G i-1 v h v h G i-1
Fig. 2: An EPG representation obtained with the canonical ordering.

We mention here that our EPG representations are quite similar to the representations of planar graphs by touching upside-down T s that is known to exist for any planar graph [START_REF] De Fraysseix | On triangle contact graphs. Combinatorics[END_REF].

(i) "Inserting" a grid line really means that all coordinates of all endpoints and bends to the right/above are increased by 1.

As for lower bounds, we can easily see that some planar graphs are not 1-bend EPG graphs, by applying Theorem 1 to the planar graph K 2,N , for N sufficiently large. We strongly suspect that some planar graphs are not 2-bend EPG graphs either (and possibly not even 4-bend EPG graphs), but this remains open.

Planar bipartite graphs

Now consider graphs that are both planar and bipartite. We have already seen in Theorem 1 that these are not always 1-bend EPG graphs, since K 2,N is planar and bipartite. Proof: It is known [START_REF] De Fraysseix | Representation of planar graphs by segments[END_REF] that every planar bipartite graph can be represented by touching horizontal and vertical line segments, i.e., vertices are assigned to disjoint open segments such that (v, w) is an edge if and only if the closure of the segments of v and w intersect. Furthermore, one can achieve that these segments are in an |A| × |B|-grid and no two segments are on the same horizontal or vertical line.

Let s h and s v be a horizontal and vertical segment that touch at point (x, y). For at least one of them, this point must be an endpoint. If only s v ends at (x, y), then add segment [x, x + 1] × y to the grid-path replacing s v . If only s h ends at (x, y), then add segment x × [y, y + 1] to the grid path replacing s h . If they both end at (x, y), then add segment x × [y, y + 1] to both (if not in s v already.) See also Figure 3. Put differently, we replace a vertical segment by a "C" and a horizontal segment by a "U", except when both segments end at the same point. We obtain a 2-bend EPG representation with the desired properties. 2

s v s h s h s v s h s v
Fig. 3: Converting a representation by touching segments into an EPG representation with at most 2 bends per path.

Outer-planar graphs and claw-free graphs

An outer-planar graph is a planar graph that can be drawn so that all vertices are on the outer-face. Since K 2,N is not an outer-planar graph (for N ≥ 3), one could suspect that these are all 1-bend EPG graphs. This is not the case.

Theorem 5 There exists an outer-planar graph that is not a 1-bend EPG graph.

Proof: The graph G shown in Fig. 4(a) is an outer-planar graph, but as we will argue now, it is not a 1-bend EPG graph. Consider a triangle in a 1-bend EPG representation. The union of three 1-bend paths cannot form a cycle in a rectangular grid, hence for each triangle the union of the paths forms a tree. It follows from the analysis of edge-intersection graphs of paths in trees [START_REF] Golumbic | The k-edge intersection graphs of paths in a tree[END_REF] that these three paths either all intersect in one grid edge (we say that they are an edge-clique), or they form a claw-clique, i.e., there exists a K 1,3 in the grid such that any degree-1 vertex of the claw is used by exactly two paths. See Fig. 4(c).

Define a 3-sun to be the graph that consists of a central triangle, and for every edge of the triangle a degree-2 vertex (called the outrigger) connected to the endpoints of the edge. From the work by Golumbic et al. [START_REF] Golumbic | Edge intersection graphs of single bend paths on a grid[END_REF], it follows that the central triangle of a 3-sun necessarily must be a claw-clique in any 1-bend EPG representation. Now consider the triangle {a, b, c} in graph G. Since it is part of an induced 3-sun, it is a claw-clique. After possible renaming, assume that a and b have a bend in common, and let a be the outrigger-vertex attached to edge (a, b). Since {a, b, a } is part of a sun, it, too, must be a claw clique. One of a and b must have a bend in that claw clique, too, say vertex a does. Since a has only one bend, the two bends in the two claw cliques must be at the same grid point, and hence a and b both have a bend in claw clique {a, b, a }, and a is drawn as a straight line. But then a and c share grid edges: a contradiction since they are not adjacent.

2

As for upper bounds, it is well-known that every outer-planar graph has a vertex ordering v 1 , . . . , v n such that each vertex v i has at most 2 earlier neighbours, i.e., neighbours in v 1 , . . . , v i-1 . We say that it is 2-regular acyclic orientable. We can give a 3-bend construction for any graph that has such an orientation (which includes more graphs, for example all series-parallel graphs, and even some non-planar graphs such as the graph obtained from K n by subdividing all edges.) Theorem 6 Every 2-regular acyclic orientable graph has 3-bend EPG representation in an n × n-grid.

Proof: Let v 1 , . . . , v n be a vertex order such that every vertex v i has at most 2 earlier neighbours. We maintain the hypothesis that the graph induced by v 1 , . . . , v i has a 3-bend EPG representation such that every vertex-path contains a horizontal grid segment and a vertical grid segment that do not intersect any other vertex-path; we call these the free segments. This is trivial for v 1 : represent it by an arbitrary vertical and horizontal segment attached to each other.

To add vertex v i to an existing drawing, find its earlier neighbours, say v j and v k . (The case of only one earlier neighbour is even easier.) Pick one grid edge e j from the vertical free segment of v j and one grid edge e k from the horizontal free segment of v k . Insert a new horizontal grid line j that splits e j , and a new vertical grid line k that splits e k . Now define a path by using one part of e j , going along j until the crossing with k , going along k until e k , and then using one part of e k . See Fig. 5.

One easily verifies that this path has three bends, intersects with the paths of v j and v k , and does not intersect any other paths. Moreover, v j and v k still have free segments (the other parts of e j and e k ), and v i also has free segments (along j and k ), so the induction hypothesis holds with the new vertex. Since every vertex adds at most one new row and column, the grid size for n vertices is n × n. We suspect that this construction is not optimal, especially for outer-planar graphs.

2 j k e k v i e j
Conjecture 1 Every outer-planar graph is a 2-bend EPG graph.

Line graphs and claw-free graphs

A graph G is a line graph if there exists a root graph H such that every vertex of G corresponds to an edge of H, and two vertices of G are adjacent if the two corresponding edges have an endpoint in common. One can easily show the following result (see also Figure 6): Let k be a vertex of H (which is an edge (i, j) in G). The path for k starts at (0, i), goes to (k, i), from there to (k, j), and from there to (0, j). One easily verifies that this is a 2-bend EPG representation.

2 One might ask whether a similar result exists for generalization of line graphs, e.g., for claw-free graphs (which are the graphs without an induced K 1,3 .) One can easily see that not all claw-free graphs have a 1-bend EPG representation: Take the graph in Figure 4(a) and contract three pairs of vertices, as shown in Figure 7. The resulting graph is claw-free. Moreover, the exact same argument as before shows that it cannot have a 1-bend EPG representation: Triangle {a, b, c} must form a claw-clique, and if (say) vertex c is the horizontal vertex in it, then {a, b, a } is a central triangle of another induced 3-sun and hence must also be a claw-clique, leading to an intersection between a and c. a b c a Fig. 7: A claw-free graph that does not have a 1-bend EPG representation.

edge in H = vertex in G in H vertex
Note that this is in contrast to claw-free chordal graphs, where is was shown very recently that they indeed have a 1-bend EPG representation (Asinowski and Ries, private communication). It remains open to show whether every claw-free graph has a 2-bend EPG representation.

Bounded pathwidth graphs

A graph of pathwidth k is a graph that has a vertex order v 1 , . . . , v n such that for any j, at most k vertices in v 1 , . . . , v j-1 have a neighbour in v j , . . . , v n .

Theorem 8 Every graph of pathwidth at most k has a 2k -2-bend EPG representation in a k × (3nk -3)-grid.

Proof: Let the vertex ordering v 1 , . . . , v n be as described above. We say that vertex i is active at time j > i if it has a neighbour in {v j , . . . , v n }; thus at most k vertices are active at any given time.

We route the vertices such that the paths of all vertices that are active at time j end in a ray to the right. v 1 simply starts as a horizontal line segment. For j > 1, consider the earlier neighbours of v j . There can be at most k of them (since all of them are active at time j). Route v j starting at the horizontal ray at one of its earlier neighbours, use one edge in common with that ray, use two bends to get to the ray of the next neighbour, and so on. The order of visiting the neighbours is irrelevant, except that the last one should be one that is not active at time j + 1, if there is such a neighbour.

Since at most k vertices are active at time j + 1, there are three possible cases (see also Fig. 8:) (1) v j has at most k -1 earlier neighbours. Then we add another two bends to the route of v j and let it end in a ray to the right. (2) v j has k earlier neighbours, and v j is not active at time j + 1. Then we end v j 's path after the common grid edge with the last neighbour. (3) v j has k earlier neighbours, and v j is active at time j + 1. Then one of the earlier neighbours, say v i , is not active at time j + 1, and v j ends in its row. We let the grid path of v i end at this point, and v j continues as a rightward ray in the row that was v i 's.

In all cases, we have used at most 2k -2 bends for v j , and all paths of vertices active at time j + 1 end in a ray to the right. We can restrict the height by using only k rows, one for each of the active vertices. As for the width, the path of v j uses only two columns except in case [START_REF] Dangelmayr | Chordal graphs as intersection graphs of pseudosegments[END_REF], where it uses four; but in case (3) the last column can be re-used for the path of v j+1 since it only contains one point from v i and hence the paths of v i and v j+1 are edge-disjoint. Since case (3) can only happen for j ∈ {k + 1, . . . , n -1} (v j must have k earlier neighbours and at least one later neighbour), and since v 1 doesn't need to use a column (it can start when v 2 starts), the bound follows.

2

v j v j v i (2) (1)
(3) v j Fig. 8: The grid path for vertex vj in the three cases of a graph of pathwidth k. Only grid paths of earlier neighbours of vj are shown.

Graphs with κ-regular edge orientations

We say that a graph has a κ-regular acyclic orientation if it has an acyclic edge orientation with i ndeg(v) ≤ κ for all vertices v. The construction in [START_REF] Golumbic | Edge intersection graphs of single bend paths on a grid[END_REF] yields that every κ-regular acyclic orientable graph has a 2κbend EPG representation.

In Theorem 6, we improved this to 3 bends for κ = 2. We suspect that such an improvement is possible in general, and any κ-regular acyclic orientable graph is a (2κ -1)-bend EPG graph. Such graphs include graphs of treewidth κ (and also graphs of pathwidth κ, though Theorem 8 provides a better bound here.)

We show here a similar bound even if the edge orientation need not be acyclic. We say that a graph G has a κ-regular orientation if G has an edge orientation such that i ndeg(v) ≤ κ for all vertices v. Theorem 9 Every κ-regular orientable graph G has a (2κ + 1)-bend EPG representation in a 2n × 2ngrid. If G is bipartite, then the representation has only 2κ bends per path.

Proof: Assume we are given a κ-regular orientation. For every vertex w, a predecessor is a vertex v for which an edge (v, w) exists and is directed v → w.

Number the vertices arbitrarily as v 1 , . . . , v n . The idea is to represent vertex v i by an L using the (2i)th column and the (2n -2i)th row (counting bottom-to-top) of a 2n × 2n-grid. Any vertex v i crosses the path of any vertex v j (j > i) at point (2i, 2n -2j). If v i → v j is an edge, then re-route v j near the crossing by adding two bends such that the paths of v i and v j share an edge. See also Fig. 9.

More precisely, the grid path for v j is defined as follows. Start at the top of column 2j. Continue until you reach the row of some predecessor v i , i < j, i.e., row 2n -2i or 2n -2i + 1. If v j has an even number of predecessors in {v 1 , . . . , v i }, then the path of v j switches from column 2j to column 2j + 1, else it switches from column 2j + 1 to column 2j. This switch is done in row 2n -2i if v i has an even number of predecessors in {v 1 , . . . , v j } and in row 2n -2i + 1 otherwise.

The grid path for v j thus continues until it reaches row 2n-2j, and thus has intersected all predecessors v i with i < j. Then the path adds one bend and continues in row 2n -2j if it was in column 2j before, and in row 2n -2j + 1 otherwise. For any predecessor v i with i > j, the path switches similarly between row 2n -2j and 2n -2j + 1, using the column of v i as determined by the parity of predecessors of v i in {v 1 , . . . , v j }.

In total, the number of bends in the path of vertex v is 2i ndeg(v) + 1, which is at most 2κ + 1. See Fig. 9. It is easy to see that the size of the grid is 2n × 2n.

If G is bipartite, then let {v 1 , . . . , v a } be one vertex class, and {v a+1 , . . . , v n } be the other. Each vertex v j with j ≤ a then has no predecessor v i with i < j, so we can omit the part of the path using columns 2j and 2j + 1 and save the bend that transitions this part to the part using rows 2n -2j and 2n -2j + 1.

Similarly we can save one bend for a vertex v j with j > a by omitting the part of the path that uses rows 2n -2j and 2n -2j + 1. Graphs with a κ-regular orientation include planar graphs (κ = 3), and planar bipartite graphs (κ = 2), though we showed bounds better than Theorem 9 for these classes already. It is known that the smallest κ for which G has a κ-regular orientation is max H⊆G |E(H)|/|V (H)| [START_REF] De Fraysseix | Regular orientations, arboricity and augmentation[END_REF]. Also, every graph is (∆+1)/2 -regular orientable: edge-colour the graph with ∆+1 colours, split the graph into (∆+1)/2 subgraphs with maximum degree 2, and orient each, such that each vertex has at most one incoming edge. Edge colourings with ∆ colours (which exist for example for bipartite graphs) gives even better bounds.

Corollary 1 Every graph is a 2 (∆+1)/2 +1-bend EPG graph. Every bipartite graph is a 2 ∆/2 -bend EPG graph.

Remarks

We leave many open problems. An obvious one is to improve the upper or lower bounds for the number of bends for all graphs where this isn't tight yet. But more pressing are complexity issues. How quickly can we recognize 1-bend EPG graphs or k-bend EPG graphs? Is this NP-hard? What are time complexities of some problems in k-bend EPG graphs for small k? Since planar graphs are 5-bend EPG graphs, the 3-Coloring problem is NP-hard in 5-bend EPG graphs. Is it polynomial for smaller k?

Fig. 1 :

 1 Fig. 1: An EPG representation of a complete bipartite graph in a 16 × 6-grid.

Theorem 2

 2 Every bipartite graph G = (A ∪ B, E) has a (2|A| -2)-bend EPG representation with grid-size |A| × 2|B|.

Theorem 4

 4 Every planar bipartite graph G = (A ∪ B, E) has a 2-bend EPG representation of size (|A| + 1) × (|B| + 1).

Fig. 4 :

 4 Fig. 4: (a) An outer-planar graph that is not a 1-bend EPG graph. (b) The 3-sun. (c) A claw-clique.

Fig. 5 :

 5 Fig. 5: The construction for 2-regular acyclic orientable graphs.

Theorem 7

 7 Every line graph has a 2-bend EPG representation in an n × (m + 1)-grid. Proof: Number the vertices of G as 1, . . . , n and the edges of G (which are vertices of H) as 1, . . . , m.

Fig. 6 :

 6 Fig. 6: 2-bend EPG representation of a line graph G with root graph H.

2

 2

Fig. 9 :

 9 Fig. 9: 5-bend EPG representation of a 2-regular orientable graph.

Supported by NSERC.


Juhani Karhumäki

Aleksi Saarela

Noneffective Regularity of Equality Languages and Bounded Delay Morphisms †

Keywords: regularity, bounded delay, Post correspondence problem

We give an instance of a class of morphisms for which it is easy to prove that their equality set is regular, but its emptiness is still undecidable. The class is that of bounded delay 2 morphisms.

Introduction

Regular (or rational) languages constitute a fundamental class of formal languages, which is typically viewed as a simple, or even the simplest class of languages. For example, decision problems on regular languages are -with a few exceptions -algorithmically decidable.

However, there also exists another viewpoint. There are some questions, which lead to regular languages, but the mechanism is so complicated that the regularity holds noneffectively (the meaning of this assertion will be explained below). A splendid example is a result of Haines (or, in fact, that of Higman) stating that the upper closure of any language under the relation of being a sparse subword is regular, see e.g [START_REF] Leonard | On free monoids partially ordered by embedding[END_REF]. Another example of this nature is the regularity of equality languages of bounded delay morphisms, which is the topic of this paper. Our goal is to give a simple -a textbook type -proof of this fundamental result.

Equality languages are sets of solutions of instances of the Post Correspondence Problem (PCP for short). Hence their emptiness is undecidable as was proved by E. Post already in 1946, see [START_REF] Post | A variant of a recursively unsolvable problem[END_REF]. Later it was revealed that their generating power is very high: each recursively enumerable language is obtained as a morphic image of an intersection of an equality language and a regular language, see e.g. [START_REF] Karel Culik | A purely homomorphic characterization of recursively enumerable sets[END_REF] or [START_REF] Karhumäki | On the power of cooperating morphisms via reachability problems[END_REF] for a recent survey. On the other hand, certain equality languages, namely those with elementary morphisms, played a crucial role in a nice solution of the celebrated D0L sequence equivalence problem, see [START_REF] Ehrenfeucht | Elementary homomorphisms and a solution of the D0L sequence equivalence problem[END_REF]. For these morphisms the equality language is regular. A further analysis revealed that the regularity was, in fact, a consequence of so-called bounded delay property, see [START_REF] Choffrut | Test sets for morphisms with bounded delay[END_REF] and [START_REF] Harju | Morphisms[END_REF].

Interesting problems arose: Is the equality language of bounded delay morphisms effectively regular? Is the PCP decidable for bounded delay morphisms? These problems were answered negatively by K.

Ruohonen in [START_REF] Ruohonen | Reversible machines and Post's correspondence problem for biprefix morphisms[END_REF]. In fact, he proved his result in a stronger form of biprefix morphisms. A drawback of his proof is that it is quite complicated. It relies, as an earlier proof showing the undecidability of PCP for injective morphisms, see [START_REF] Lecerf | Récursive insolubilité de l'équation générale de diagonalisation de deux monomorphismes de monoïdes libres ϕx = ψx[END_REF], on reversible Turing machines. However, an equality set of injective morphisms need not be regular, see [START_REF] Karhumäki | A note on elementary homomorphisms and the regularity of equality sets[END_REF].

Our goal here is to give an instance of a class of morphisms for which the PCP is undecidable, and the equality languages are regular, and moreover the proofs of these results are short. Our family is that of morphisms with bounded delay 2. Our proofs use the ideas of [START_REF] Ruohonen | Reversible machines and Post's correspondence problem for biprefix morphisms[END_REF], but allow simpler constructions, and consequently shorter proofs.

We will briefly outline the structure and constructions in this paper. We use the halting problem of Turing machines on empty input as our undecidable problem. We want to simulate their computations by the equality mechanism of two cooperating morphisms. It is well known that this can be done. However, the morphisms need not possess a bounded delay property. A key idea is here that instead of using normal configurations of Turing machines we use so-called extended configurations which contain some extra local information. This makes it possible to do the above simulation by bounded delay morphisms. The whole approach does not require the use of so-called reversible Turing machines, as was crucial in [START_REF] Ruohonen | Reversible machines and Post's correspondence problem for biprefix morphisms[END_REF], although some ingredients of reversible Turing machines motivate the definition of extended configurations. As a consequence we obtain a direct and relatively simple proof for the undecidability of PCP for bounded delay morphisms.

Notions

We assume that the reader is familiar with the basics of automata theory and combinatorics on words, see e.g. [START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF], [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF] and [START_REF] Choffrut | Combinatorics of words[END_REF]. For more on morphisms of free monoids we refer to [START_REF] Harju | Morphisms[END_REF]. We only recall here that the notation u ≤ v is used to specify that word u is a prefix of word v, and that words u and v are comparable if u ≤ v or v ≤ u.

The equality language of two morphisms f, g : Σ * → Γ * is the set

E(f, g) = w ∈ Σ + : f (w) = g(w) . (1)
The PCP asks whether this language is empty or not. The modified PCP asks whether the language E(f, g) ∩ aΣ * is empty for a given letter a ∈ Σ.

A morphism h : Σ * → Γ * is of bounded delay n, if there are no letters a, b ∈ Σ and words u, v ∈ Σ n , for which a = b and h(au) ≤ h(bv). Further it is of bounded delay if it is so for some n.

An instantaneous description (ID) of a Turing machine (TM) at some point of its computation is u(q, a)v, where q is the current state, a is the symbol under the head, and u and v are the parts to the left and to the right of it. So every computation has a sequence of associated IDs, each of which describes the configuration of the machine at one step of the computation.

The article [START_REF] Ruohonen | Reversible machines and Post's correspondence problem for biprefix morphisms[END_REF] contains two constructions of TMs: First, for an arbitrary TM M an equivalent reversible machine M is constructed. Second, an equivalent so-called synchronized modulo 2 machine M is constructed for M . We do not need these constructions. First reversible TMs were constructed already in 1970s, see [START_REF] Bennett | Logical reversibility of computation[END_REF], but their importance has increased after the invention of quantum computing, see [START_REF] Hirvensalo | Quantum Computing[END_REF].

Extended Instantaneous Descriptions

Our goal is to prove the undecidability of the PCP for bounded delay morphisms. We will do this by reducing it to the halting problem of TMs on empty input. More precisely, for an arbitrary TM we will construct two bounded delay morphisms such that their equality set contains a word starting with a specific letter if and only if the machine accepts the empty word.

In a standard proof of the undecidability of the PCP a computation of a TM is simulated with two morphisms, which operate on IDs (see e.g. [START_REF] Karhumäki | On the power of cooperating morphisms via reachability problems[END_REF]). We wish to do this simulation with bounded delay morphisms. One of the problems in this approach is that a bounded delay morphism is necessarily injective on letters, but the transition function of a TM can be non-injective. This is why we will in this section define extended instantaneous descriptions. In the next section we will then define the bounded delay morphisms, which will operate on these extended configurations, and prove the results.

Let M = (Q, Σ, Γ, δ, q 0 , * , {h}) be a deterministic TM, where Q is the set of states, Σ is the input alphabet, Γ is the tape alphabet, δ is the (partial) transition function, q 0 is the initial state, * is the blank symbol and h is the halting state. For convenience, we assume that M never enters q 0 , always halts in h and never writes * .

Example 3.1 Let M = ({q 0 , h}, {a}, {a, * }, δ, q 0 , * , {h}), where δ(q 0 , * ) = (h, a, R). If the input is empty, then M will write a, move to the right and halt. The IDs of this computation are (q 0 , * ) and a(h, * ).

Let ∆ = Γ ∪ (Q × Γ). Let Θ = ∆ × ({S} ∪ (Q × Γ))
, where S is a new symbol. We write the second component of an element of Θ below the first component. For example, if q ∈ Q and a ∈ Γ, then

(q, a) S , a (q,a) ∈ Θ. (2)
We define extended instantaneous descriptions (EID) of the computation of M with empty input. Every EID will be an element of (Q × Γ) * #Γ * Θ∆ * $, where # and $ are new symbols. The initial EID is

β 0 = #(q 0 , * ) S $.
(3)

The next rows define the rules β i → β i+1 with which we can derive the next EID β i+1 from an EID β i .

Here

a, b, c, b ∈ Γ, a, c, b = * , q, q ∈ Q, y, z ∈ ∆, u 1 ∈ (Q × Γ) * , u 2 ∈ Γ * and u 3 ∈ ∆ * . u 1 #u 2 a S zu 3 $ → u 1 #u 2 az S u 3 $, (4)
u 1 #u 2 a(q, b) S u 3 $ → u 1 #u 2 (q , a) (q,b) b u 3 $, if δ(q, b) = (q , b , L), (5)
u 1 #(q, b) S u 3 $ → u 1 #(q , * ) (q,b) b u 3 $, if δ(q, b) = (q , b , L), (6)
u 1 #u 2 (q, b) S cu 3 $ → u 1 #u 2 b (q , c) (q,b) u 3 $, if δ(q, b) = (q , b , R), (7)
u 1 #u 2 (q, b) S $ → u 1 #u 2 b (q , * ) (q,b) $, if δ(q, b) = (q , b , R), (8)
u 1 #u 2 a y (q,b) u 3 $ → u 1 #u 2 a (q,b) yu 3 $, (9)
u 1 # y (q,b) u 3 $ → u 1 (q, b)#y S u 3 $. ( 10
)
So if β i → β i+1 for i = 0, 1, 2, . . . , then β 0 , β 1 , β 2 , . . . are the EIDs. This sequence of EIDs can be finite or infinite. It can be easily seen that for every EID β i there is at most one EID β i+1 such that β i → β i+1 , so the sequence is unique.

The idea of EIDs is that the part to the left of # contains the state-symbol-pairs of the computation up to some point, and the part between # and $ becomes an ID, if the element of Θ is replaced with its first component. It is important that two consecutive EIDs differ only in one place. This is why the element of Θ moves back and forth and carries information in its second component. Lemma 3.3 and its proof explain how EIDs work.

Example 3.2 Let M be the TM of Example 3.1. The EIDs are

#(q 0 , * ) S $, #a(h, * ) (q0, * ) $, # a (q0, * ) (h, * )$, (q 0 , * )#a S (h, * )$, (q 0 , * )#a(h, * ) S $. (11)
The next lemma shows the relation between IDs and EIDs.

Lemma 3.3 Let α 0 , α 1 , α 2 , . . . be the IDs and β 0 , β 1 , β 2 , . . . the EIDs of the computation of M with empty input. Let α i = u i x i v i , where u i , v i ∈ Γ * and x i ∈ Q × Γ. Now there are 0 = j 0 < j 1 < j 2 < . . . such that

β ji = x 0 . . . x i-1 #u i x i S v i $. ( 12
)
Proof: Clearly (12) holds for i = 0. We assume that it holds for i and prove that

β ji → + x 0 . . . x i #u i+1 x i+1 S v i+1 $, (13)
where → + is the transitive closure of →. (Naturally we assume here that α i is not the last ID, that is δ(x i ) and thus α i+1 are defined.) By using one of the rules (5)-( 8), we simulate one step of the computation and end up with the EID

β ji+1 = x 0 . . . x i-1 #u i+1 x i+1 xi v i+1 $. (14)
By using rule (9) sufficiently many times and then rule (10), we get the EID

x 0 . . . x i #y S v$, (15)
where yv = α i+1 . By using rule (4) sufficiently many times we get the required EID β ji+1 .

Morphisms

Like in the previous section, we will consider a TM M = (Q, Σ, Γ, δ, q 0 , * , {h}), and we will use the notation,

∆ = Γ ∪ (Q × Γ), ∆ 1 = ∆ ∪ {#, $} and Θ = ∆ × ({S} ∪ (Q × Γ)).
We will define two bounded delay morphisms g 1 , f 1 : A * → B * , which will simulate the computation of M with empty input. The alphabet B is the same as that used by EIDs, that is B = ∆ 1 ∪ Θ. For every u ∈ B * we define a letter [u]. The alphabet A will consist of a finite number of these letters. The morphism g 1 is defined so that g 1 ([u]) = u. The first column of Table 1 gives the values of g 1 on the letters of A, and thus it also implicitly defines the alphabet A. The second column gives the values of f 1 on these letters. In the table

a, b, c, b ∈ Γ, a, c, b = * , q, q ∈ Q, x ∈ Γ ∪ {#}, y ∈ ∆ and z ∈ ∆ 1 .
There is a correspondence between the rows of the table and the rules (4)-(10) in the definition of EIDs.

Tab. 1: Morphisms g1 and f1

u = g 1 ([u]) f 1 ([u]) z z xa S z xaz S z = (q 0 , * ), z ∈ ∆ a(q, b) S z (q , a) (q,b) b z δ(q, b) = (q , b , L) #(q, b) S z #(q , * ) (q,b) b z δ(q, b) = (q , b , L) x(q, b) S c xb (q , c) (q,b) δ(q, b) = (q , b , R) x(q, b) S $ xb (q , * ) (q,b) $ δ(q, b) = (q , b , R) a y (q,b) z a (q,b) yz # y (q,b) z (q, b)#y S z y = (q 0 , * )
The next lemma shows that g 1 and f 1 simulate M in the sense that if g 1 "reads" an EID, then f 1 "writes" the next EID.

Lemma 4.1 Let β j , β j+1 be two consecutive EIDs. There is a word u ∈ A * such that g 1 (u) = β j and

f 1 (u) = β j+1 . Further, if β j ≤ g 1 (v) or β j+1 ≤ f 1 (v), then u ≤ v. Proof: Let β j = x 1 . . . x m Xy 1 . . . y n , where x i , y i ∈ ∆ 1 and X ∈ Θ. If β j ≤ g 1 (v), then v must begin with u = [x 1 ] . . . [x m-1 ][x m Xy 1 ][y 2 ] . . . [y n ]. Now g 1 (u) = β j . By comparing the rules (4)-(10) with Table 1 it can be verified that f 1 (u) = β j+1 . If β j+1 ≤ f 1 (v), then similarly it can be seen that v begins with u = [x 1 ] . . . [x m-1 ][x m Xy 1 ][y 2 ] . . . [y n ]. 2
The morphisms f 1 and g 1 are almost sufficient for simulating M , but we must extend them to handle initialization and termination. Initialization is easy, because there is only one initial EID, but termination is hard, because there are many potential final EIDs. This problem is handled by running the simulation backwards, which requires more complicated notation. The reversibility of a computation, which is enabled by the use of EIDs instead of IDs, is implicitly present here, as well as later in the proof of Lemma 4.4.

For some elements x ∈ Θ we need a separate copy of x. This will be denoted by x. For some other elements x we want x and x to be equal. So we define a mapping x → x as follows: If x = (h, a)

S

, where a ∈ Γ, let x = x. For every other x ∈ Θ, let x be a copy of x. Further, for every x ∈ ∆ 1 , let x = x. Finally, let B = {x : x ∈ B} and Θ = {x : x ∈ Θ}. We extend the mapping x → x to a morphism B * → (B ∪ B) * . Note that

B ∩ B = ∆ 1 ∪ (h, a) S : a ∈ Γ . ( 16
) If t = [u], where u ∈ B * , let t = [u]. Let A = t : t ∈ A . We extend also this mapping [u] → [u] to a morphism A * → (A ∪ A) * . Note that A ∩ A = {[x] : x ∈ ∆ 1 } .
We define two bounded delay morphisms g, f :

(A ∪ A ∪ {I, T }) * → (B ∪ B ∪ {I, T }) * : g(t) =            g 1 (t) if t ∈ A, f 1 (s) if t = s ∈ A, I if t = I, #(q 0 , * ) S $T if t = T , f (t) =            f 1 (t) if t ∈ A, g 1 (s) if t = s ∈ A, I#(q 0 , * ) S $ if t = I, T if t = T . ( 17
)
Here I and T are new symbols. If t ∈ A ∩ A, then g 1 (t) = f 1 (t) and f 1 (t) = g 1 (t), so f and g are well defined.

Lemma 4.2 If M does not accept the empty word, then the set {w ∈ E(f, g) : I ≤ w} is empty, and if M does accept the empty word, then the set contains a unique minimal word (minimal with respect to the prefix ordering).

Proof: Let the EIDs of M be β 0 , β 1 , β 2 , . . . If the computation of M does not halt, this will go on forever, and f (Iw) and g(Iw) can never match. If the computation stops in a nonhalting state, then there is no way to continue. So if M does not accept the empty word, then f (Iw) = g(Iw) for all w.

If the computation halts and β n is the last EID, then f (Iu 0 . . . u n-1 ) = g(Iu 0 . . . u n-1 )β n and β n = β n . By Lemma 4.1, if f (Iw) = g(Iw)β k+1 and β k → β k+1 , then we must continue with g(u k ) = β k+1 and f (u k ) = β k .

So if w = u 0 . . . u n-1 u n-1 . . . u 0 , then f (Iw) = g(Iw)β 0 , and IwT is the unique minimal word such that f (IwT ) = g(IwT ). 2

Example 4.3 Let M be the TM of Examples 3.1 and 3.2. Now

g(w) = f (w) = I#(q 0 , * ) S $#a(h, * ) (q0, * ) $# a (q0, * ) (h, * )$ • (q 0 , * )#a S (h, * )$(q 0 , * )#a(h, * ) S $(q 0 , * )#a S (h, * )$ • # a (q0, * ) (h, * )$#a(h, * ) (q0, * ) $#(q 0 , * ) S $T, (18)
where w = I[#(q 0 , * )

S $][#][a(h, * ) (q0, * ) $][# a (q0, * ) (h, * )][$] • [(q 0 , * )][#a S (h, * )][$][(q 0 , * )][#a S (h, * )][$][# a (q0, * ) (h, * )][$] • [#][a(h, * ) (q0, * ) $][#(q 0 , * ) S $]T. (19)
Lemma 4.4 The morphisms g and f are of bounded delay 2.

Proof: We will prove this for g; the case of f is similar. The bounded delay condition of g can be violated in two ways: for two different letters r, s, either g(r) = g(s) (which always violates it), or g(r) < g(s) (which may or may not violate it). We will prove that the first case will not happen, and that if g(r) < g(s), then there are no letters p, q such that g(rpq) and g(s) are comparable. This means that g is of bounded delay 2. Assume that g(r) = g(s).

If f 1 ([u]) = f 1 ([v]), then also g 1 ([u]) = g 1 ([v]) by Table 1. If g 1 ([u]) = g 1 ([v]), then u = v, because g 1 ([u]) = u and g 1 ([v]) = v.
From this it follows that if r, s ∈ A, then r = s, and the same holds if r, s ∈ A. If r ∈ A A and s ∈ A A, then g(r) = g(s), because g(s) contains an element of Θ and g(r) does not. Finally, if r = I, then s = I, and if r = T , then s = T . It follows that g is injective on letters.

Assume that g(r) < g(s). Now g(s) contains X ∈ Θ ∪ Θ, but g(r) does not contain it. If g(rpq) and g(s) are comparable, then g(p) or g(q) contains this X, but on a different position. This is impossible, because if X is a factor of g(s) and g(t), where t ∈ {p, q}, then its position in g(s) and g(t) is the same. This can be verified from Table 1. 2

Theorem 4.5 For any TM M we can construct two bounded delay 2 morphisms f, g and specify a letter I so that if M does not accept the empty word, then the set {w ∈ E(f, g) : I ≤ w} is empty, and if M does accept the empty word, then the set contains a unique minimal word.

Proof: Follows from Lemma 4.2 and from Lemma 4.4. 2

The undecidability result now follows with standard techniques.

Theorem 4.6 The PCP for bounded delay 2 morphisms is undecidable.

Proof: For any TM M we can construct the morphisms f and g of Theorem 4.5. If the modified PCP for bounded delay morphisms would be decidable, then it could be decided whether M accepts the empty word, but this is not possible. The undecidability of the ordinary PCP for bounded delay morphisms follows easily from the modified version (see also [START_REF] Harju | Morphisms[END_REF]). For arbitrary bounded delay 2 morphisms f, g : Σ * 1 → Σ * 2 and letter I ∈ Σ 1 we will construct bounded delay 2 morphisms f , g : (Σ 1 ∪ {i, t}) * → (Σ 2 ∪ {i, t, X}) * such that {w ∈ E(f, g) : I ≤ w} is empty if and only if E(f , g ) is empty (here i, t, X are new symbols).

Define morphisms l, r by l(a) = Xa and r(a

) = aX. Let f (x) = l(f (x)) for x ∈ Σ 1 , f (i) = il(f (I)) and f (t) = Xt. Let g (x) = r(g(x)) for x ∈ Σ 1 , g (i) = iXr(f (I)) and g (t) = t. Now f and g are of bounded delay 2. If f (w) = g (w) = 1, then w = iutv, where u ∈ Σ * 1 , and f (Iu) = g(Iu). If f (Iu) = g(Iu), then f (iut) = g (iut). So {w ∈ E(f, g) : I ≤ w} is empty if and only if E(f , g ) is empty.
2

Regularity of the Equality Set

To conclude our presentation we recall that the equality sets of bounded delay morphisms are regular. For the sake of completeness we present a short proof of this. More details can be found in [START_REF] Harju | Morphisms[END_REF]. Actually, even a stronger result is proved in [START_REF] Choffrut | Test sets for morphisms with bounded delay[END_REF].

Theorem 5.1 Let f, g : Σ → Γ be morphisms of bounded delay. The language E(f, g) is regular.

Proof: Because f is of bounded delay, there is a number N such that if v ∈ Γ N , then for at most one a ∈ Σ there is a w ∈ Σ * such that v ≤ f (a)f (w). The same holds for g. We assume that N is a suitable bound for both morphisms f and g. We construct a deterministic automaton accepting E(f, g) ∪ {1}. Let Q = (Γ * × {1}) ∪ ({1} × Γ * ) be the set of states and let

δ((u, v), a) =          (u , 1) if v = 1 and uf (a) = g(a)u , (1, v ) if v = 1 and uf (a)v = g(a), (u , 1) if u = 1 and f (a) = vg(a)u , (1, v ) if u = 1 and f (a)v = vg(a), (20)
where (u, v) ∈ Q and a ∈ Σ, be the (partial) transition function. So δ((u, v), a) is well defined, if uf (a) and vg(a) are comparable, and undefined otherwise.

Let (u, v), (u , v ) ∈ Q and w ∈ Σ * . Now δ((u, v), w) = (u , v ), if uf (w)v = vg(w)u , and δ((u, v), w) is undefined, if uf (w) and vg(w) are not comparable. In particular, δ((1, 1), w) = (1, 1) if and only if f (w) = g(w). Thus the automaton (Q, Σ, δ, (1, 1), {(1, 1)}), where (1, 1) is the initial state and {(1, 1)} is the set of final states, would accept E(f, g) ∪ {1}, but Q is not finite. Restricting the automaton to the states occurring in chains of transitions of the form (1, 1) → q 1 → • • • → q n → (1, 1) does not change the accepted language. We show that the set Q of these states is finite, which proves the theorem.

Let Q 1 = {(u, v) ∈ Q : |uv| < N } and let Q 2 be the set of those states in Q Q 1 to which there is a transition from Q 1 . The sets Q 1 and Q 2 are finite. If (u, v) ∈ Q Q 1 , a ∈ Σ and δ((u, v), a) ∈ Q , then δ((u, v), aw) = (1, 1) for some w ∈ Σ * . This means that uf (a)f (w) = vg(a)g(w). Thus either u = 1, |v| ≥ N and v ≤ f (a)f (w), or v = 1, |u| ≥ N and u ≤ g(a)g(w). In both cases a is uniquely determined because of the bounded delay property, so from each q ∈ Q Q 1 there is a transition to only one state of Q . Thus for each q ∈ Q 2 there is only one chain of the form q → q 1 → • • • → q n ∈ Q 1 , where q 1 , . . . , q n-1 / ∈ Q 1 . Let Q 3 be the set of states in these chains. Because Q 2 is finite and each of these chains is finite, also Q 3 is finite. If q ∈ Q Q 1 , there is a chain of transitions from (1, 1) to q, and another from q to (1, 1). The former chain necessarily contains a state of Q 2 . Thus q ∈ Q 3 . This means that

Q = Q 1 ∪ Q 3 , so Q is finite. 2
To summarize, we have proved:

Theorem 5.2 The equality language of bounded delay 2 morphisms is regular, but cannot be found algorithmically, and PCP for these morphisms is undecidable.

We conclude by emphasizing that our Theorem 5.2 is not the strongest possible -K. Ruohonen proved in [START_REF] Ruohonen | Reversible machines and Post's correspondence problem for biprefix morphisms[END_REF] a stronger result (for biprefix morphisms instead of bounded delay morphisms). However, our proof and constructions are much simpler, and can be viewed as "textbook proofs" of this important result.

  . The only way to start is with f (I) and g(I). Then f (I) = g(I)β 0 . By Lemma 4.1, if f (Iw) = g(Iw)β k and β k → β k+1 , then we must continue with g(u k ) = β k and f (u k ) = β k+1 , where u k ∈ A * .

† Supported by the Academy of Finland under grant 121419 1365-8050