Sylvain Salvati

MIX is a 2-MCFL and the word problem in Z 2 is solved by a third-order collapsible pushdown automaton

Keywords: formal language theory, mildly context sensitive languages, IO and OI hierarchies, higher-order collapsible pushdown automata, group languages, algebraic topology, Jordan curves

In this work we establish that the language M IX = {w ∈ {a; b; c} * ||w| a = |w| b = |w| c } and the language O 2 = {w ∈ {a; a; b; b}||w| a = |w| a ∧ |w| b = |w| b } are 2-MCFLs. As 2-MCFLs form a class of languages that is included in both the IO and OI hierarchies, and as O 2 is the group language of a simple presentation of Z 2 we exhibit here the first, to our knowledge, non-virtually-free group language (i.e. non-context-free group language) that is captured by the IO and OI hierarchies. Moreover, it was a long-standing open problem whether MIX was a mildly context sensitive language or not, and it was conjectured that it was not, so we close this conjecture by giving it a negative answer.

Introduction

The language M IX = {w ∈ {a; b; c} * ||w| a = |w| b = |w| c }, has been introduced by Emmon Bach in [START_REF] Bach | Discontinuous constituents in generalized categorial grammars[END_REF] and [START_REF] Bach | Categorial grammars as theories of language[END_REF] as a language that proves that the scramble of a context free language may not be context free. This language is also called the Bach language after Geoffrey Pullum [START_REF] Pullum | Context-freeness and the computer processing of human languages[END_REF]. Through the enterprise of Aravind Joshi et al. [START_REF] Aravind | Tree-adjoining grammars: How much context sensitivity is required to provide reasonable structural descriptions[END_REF] [START_REF] Weir | Characterizing mildly context-sensitive grammar formalisms[END_REF] [JSW91] of defining the properties of the class of languages that captures human languages, i.e. the class of mildly context sensitive languages, the language M IX has had some importance. Indeed, as it is seen as an extreme case of the degree of free word order permitted in a language[;] this extreme case is linguistically not relevant [START_REF] Aravind | Tree-adjoining grammars: How much context sensitivity is required to provide reasonable structural descriptions[END_REF]. Following this view, M IX should be excluded from any reasonable class of languages claiming to capture natural languages. It was conjectured in [START_REF] Aravind | Tree-adjoining grammars: How much context sensitivity is required to provide reasonable structural descriptions[END_REF] that M IX should not be a Tree Adjoining Language, but there is still no proof of that property which is commented in [START_REF] Aravind | The converence of mildly context-sensitive grammar formalisms[END_REF] as being a very difficult problem and that it is not even known whether it is an indexed language.

An apparently unrelated problem has attracted the attention of the community of computational group theory. The word problem for a finitely presented (i.e. with a finite number of defining relations) group G with finitely many generators Σ consists in checking whether a word in Σ * is equal to the unit of G. This problem is in general undecidable [START_REF] Sergeyevich | On the algorithmic unsolvability of the word problem in group theory[END_REF] [Boo58] (a quite elegant proof can be found in [START_REF] Lafont | Réécriture et problème du mot[END_REF]). So given a finitely presented group G finitely generated by Σ, the group language defined by this presentation of G is the subset of Σ * which contains all the words that are equal to the unit of G. Different presentations of a same group define different group languages but these languages can be translated in each other by rational transductions. A general question (see [START_REF] Anisimov | Group languages[END_REF]) consists in relating algebraic properties of finitely presented and finitely generated groups with language-theoretic properties of their group languages. Such a question can be partially answered by characterizing the groups whose group-languages belong to a certain class of languages that is closed under rational transduction (i.e. a full trio or rational cone [START_REF] Ginsburg | Studies in abstract families of languages[END_REF]). It is already known that the groups whose group languages are regular languages are precisely finite groups and that the ones whose group languages are context-free languages are virtually free groups [START_REF] Muller | Groups, the theory of ends, and context-free languages[END_REF]. The group language of a simple presentation of Z 2 is the 2-dimensional origin-crossing language (using the terminology and notation of [START_REF] Michael | Real-time solutions of the origin-crossing problem[END_REF])

O 2 = {w ∈ {a; ā; b; b} * ||w| a = |w| ā ∧ |w| b = |w|b}
which is known not to be context-free. An open problem in computational group theory is whether O 2 is an indexed language. We will see in section 3 that actually the problems whether M IX and O 2 are indexed languages are in fact equivalent. This shows that this group theoretic question and Joshi's conjecture about M IX are equivalent.

In this paper, we do not solve these open questions, but we prove that M IX and O 2 are 2-Multiple Context Free Languages (MCFL) as defined in [START_REF] Seki | On multiple context free grammars[END_REF]. Because MCFLs fall into the class of mildly context sensitive languages that is widely believed to be the class of languages that captures natural languages, it shows that M IX is mildly context sensitive in the sense of [START_REF] Aravind | The converence of mildly context-sensitive grammar formalisms[END_REF]. The proof of this result sheds some light on whether M IX and O 2 are indexed languages, because the grammar we propose crucially relies on non-well-nested rules which are known to be able to generate languages that are not indexed (see [START_REF] Michaelis | An additional observation on strict derivational minimalism[END_REF] and [START_REF] Kanazawa | The copying power of wellnested multiple context-free grammars[END_REF]). Finally, the fact that M IX is a mildly context sensitive language is a new result that should be taken into consideration in the debate of defining the class of formal languages in which human languages lie. Furthermore, MCFLs are included in the intersection of IO and OI hierarchies [START_REF] Damm | The IO-and OI-hierarchies[END_REF] which can be seen as generalizations of macro languages as defined by Fischer [START_REF] Michael | Grammars with macro-like productions[END_REF], and in particular, the OI hierarchy generalizes the notion of indexed languages. As the languages of the OI hierarchy are also captured by higher-order collapsible automata, this shows that this class of automata can solve the word problem for Z 2 .

Interestingly, the way we prove that M IX and O 2 fall within the class of MCFLs relies on a geometric argument that involves algebraic topology. Thus, most of the proof depends on a Theorem on Jordan curves that may present an interest on its own. The paper is structured as follows: section 2 presents some preliminaries, it introduces the notion of Multiple Context Free Grammars and some notions from algebraic topology that play a key role in our proof. In section 3, assuming a Theorem on Jordan curves we prove that M IX and O 2 are 2-MCFLs. Section 4 gives the proof of the Theorem on Jordan curves we had admitted so far. Finally section 5 discusses some consequences of the result and some open problems.

Preliminaries

This section presents the mathematical tools we use in the paper.

Multiple Context Free Grammars

We write [n] for the set {1; . . . ; n} and N for the set of natural numbers. For a given finite set Σ, we write Σ * for the monoid freely generated by Σ, the elements of Σ are called letters while the elements of Σ * are called strings or words. Given a word w, we write |w| for its length, and |w| x for the number of occurrences of the letter x in w. A factor of a word w is a word w such that w = w 1 w w 2 for some w 1 and w 2 in Σ * ; w is a left factor if w 1 = and it is a right factor if w 2 = . The set of factors of w is denoted by F(w). A factor, a left factor or a right factor is said trivial when it is equal to the empty string and non-trivial otherwise. The word w = v 1 . . . v n is a subword of w if w = u 0 v 1 u 1 . . . v n u n . The set of subwords of w is denoted by S(w). If w = a 1 . . . a n where, for each i in [n], a i is a letter we write perm(w) for the set of strings defined as: prem(w) = {a σ(1) . . . a σ(n) |where σ is a pemutation of [n]}.

A ranked alphabet Ω is a pair (A, ρ) where A is a finite set and ρ is a function from A to N. Given a in A, ρ(a) is the rank of a. We shall write Ω (n) for the set {a ∈ A | ρ(a) = n}.

A Multiple Context Free Grammar (MCFG) G is a tuple (Ω, Σ, R, S) where Ω is a ranked alphabet, Σ is a finite set of letters, R is a set of rules and S is an element of Ω (1) . The rules in R are of the form

A(α 1 , . . . , α n ) :-B 1 (x 1 1 , . . . , x 1 l1 ), . . . , B p (x p 1 , . . . , x p lp )
where A is in Ω (n) , B j is in Ω (lj ) , the x k j are pairwise distinct variables and the

α j are elements of (Σ ∪ X) * with X = {x k j | k ∈ [p] ∧ j ∈ [l k ]
} and the restriction that each x k j may have at most one occurrence in the string α 1 • • • α n . Note that p may be equal to 0 in which case the right part of the rule (the one on the right of the :-symbol) is empty, in such a case we will write the rule by omitting the symbol :-.

An MCFG such as G defines judgments of the form G A(s 1 , . . . , s n ) where A is in Ω (n) and s i belongs to Σ * . Such a judgment is said to be derivable when there is a rule A(α 1 , . . . , α n ) :-B 1 (x 1 1 , . . . , x 1 l1 ), . . . , B p (x p 1 , . . . , x p lp ) and there are derivable judgments G B k (w k 1 , . . . , w k l k ) for all k in [p] such that s j is equal to α j where the possible occurrences of the x k j are replaced by w k j . The language defined by G is the set {w ∈ Σ * | S(w) is derivable}.

An MCFG G = (Ω, Σ, R, S) is a k-MCFG when the maximal arity of the elements of Ω is less than k. It is known [START_REF] Seki | On multiple context free grammars[END_REF] that for each k, k-MCFLs, the languages definable by k-MCFG, form substitution-closed full Abstract Family of Languages [START_REF] Ginsburg | Studies in abstract families of languages[END_REF]. In particular, this implies that k-MCFLs form a class of languages that is closed under rational transduction for every k. Furthermore k-MCFLs form a strictly increasing hierarchy of languages.

The notion of MCFG has been introduced in [START_REF] Seki | On multiple context free grammars[END_REF] and MCFLs form a very robust class of languages that is captured by a very wide variety of formalisms. This class of languages is exactly captured by Linear Context Free Rewritting Systems (LCFRSs) [START_REF] Weir | Linear context-free rewriting systems and deterministic tree-walking transducers[END_REF], Multi-Component Tree Adjoining Grammars (MCTAGs) [START_REF] Aravind | The converence of mildly context-sensitive grammar formalisms[END_REF], string languages definable by Hyperedge Replacement Grammars (HR) [START_REF] Weir | Linear context-free rewriting systems and deterministic tree-walking transducers[END_REF], string languages definable by second order Abstract Categorial Grammars (ACGs) [START_REF] De | On the expressive power of abstract categorial grammars: Representing context-free formalisms[END_REF] and [START_REF] Salvati | Encoding second order string acg with deterministic tree walking transducers[END_REF]. Furthermore, since MCTAGs are considered as mildly context sensitive in [START_REF] Aravind | The converence of mildly context-sensitive grammar formalisms[END_REF], MCFLs can be thus considered as mildly context sensitive languages as defined by Joshi [START_REF] Aravind | Tree-adjoining grammars: How much context sensitivity is required to provide reasonable structural descriptions[END_REF].

The relationship of MCFLs with second order ACGs shows that MCFLs are embedded in both IO and OI hierarchies [START_REF] Damm | The IO-and OI-hierarchies[END_REF]. As in [START_REF] De | On the expressive power of abstract categorial grammars: Representing context-free formalisms[END_REF], it is showed that LCFRS can be represented with a second order ACG whose lexicon has complexity 4, i.e. a level 3 IO or OI grammar. Even though, it was proved in [START_REF] Damm | An automata-theoretical characterization of the OI-hierarchy[END_REF] that OI grammars could be recognized by higher-order pushdown automata, it has been done under an implicit restriction, that of safety, that has been made explicit later on in [START_REF] Knapik | Higherorder pushdown trees are easy[END_REF]. Since then, it is still an open problem whether safe grammars generate the same class of languages as unsafe grammars, and the representation of MCFLs as OI-grammars are unsafe. Notice that level 2 safe grammars and level 2 unsafe grammars have been proved to define the same class of languages [START_REF] Aehlig | Safety is not a restriction at level 2 for string languages[END_REF], but it is still unclear whether the technique that Aehlig et al. have used can be generalized for higher levels. Nevertheless, Hague et al. [START_REF] Hague | Collapsible pushdown automata and recursion schemes[END_REF] have proposed an model of automaton that captures the same class of languages as unsafe grammars, higher-order collapsible automata such that level n OI languages can be recognized by n thorder collapsible automata. So that we have the following fact: Fact 1. Every MCFL can be recognized with a third-order collapsible pushdown automaton.

An MCFG is said well-nested when all its rules:

A(α 1 , . . . , α n ) :-B 1 (x 1 1 , . . . , x 1 l1 ), . . . , B p (x p 1 , . . . , x p lp )
verify the following properties (where

X = {x k j | k ∈ [p] ∧ j ∈ [l k ]}): • for i ∈ [p], if j < l i then α 1 . . . α n ∈ (Σ ∪ X) * x i j (Σ ∪ X) * x i j+1 (Σ ∪ X) * , • if i = i , j < l i and j < l i , then α 1 . . . α n / ∈ (Σ ∪ X)x i,j (Σ ∪ X) * x i j (Σ ∪ X) * x i j+1 (Σ ∪ X) * x i j +1 (Σ ∪ X) * .
This means that the variables of introduced in the right-hand side of the rule appear in the same order in its left hand-side and that furthermore, whenever, for some i different from i, x i j occurs in between x i j and x i j+1 in α 1 . . . α n , then for all j in [l i ] the variable x i j occurs in between x i j and x i j+1 . The rules that satisfy these conditions are called well-nested rules and the class of languages that can be defined with well-nested MCFG is called well-nested Multiple Context Free Languages and written MCFL wn .

Even though this restriction may seem intricate, it decreases the expressive power of MCFGs significantly and MCFL wn is a very natural class of languages that coincides with many formalisms, like non-duplicating IO and OI grammars (so that MCFL wn are included in indexed languages), second order ACGs of complexity 3, coupled context-free grammars [START_REF] Kanazawa | The convergence of well-nested mildly contextsensitive grammar formalisms[END_REF]. Furthermore, whereas there is still no strong form of pumping lemma for MCFL [START_REF] Kanazawa | Generating control languages with abstract categorial grammars[END_REF], there is one for MCFL wn [START_REF] Kanazawa | The pumping lemma for well-nested multiple context-free languages[END_REF].

Curves and Homotopy

We write R for the set of real numbers equipped with the usual topology and C for the set of complex numbers also equipped with the usual topology. Given a and b in R, we write [a; b] for the set We now introduce some basic notions of algebraic topology, for more details see [START_REF] Spanier | Algebraic Topology[END_REF]. Given a topological space X, an arc in X is a continuous function from [0, 1] to X. Given an arc f in X such that f (0) = A and f (1) = B, we say that f is an arc from A to B. An arc f in X is said simple or is called a Jordan arc if f is an injection into X. An arc f in X is said to be a closed curve if f (0) = f (1) and a closed curve f is said simple or is called a Jordan curve when the restriction of f to [0; 1) is an injection into X. Given a closed curve f in X such that f (0) = A, we say that f has base point A. In what follows given an arc f and R ⊆ [0; 1], we shall write f |R to denote the restriction of f to R. In particular, when R is the interval [a; b], we will make the confusion between f |[a;b] and the arc

{(1 -t)a + tb | 0 ≤ t ≤ 1}, (a; b), for the set {(1 -t)a + tb | 0 < t < 1}, [a; b) for the set {(1 -t)a + tb | 0 < t ≤ 1}
f (t) = f (a + t(b -a)). When a = b, we will call f |[a;b] a subarc of f and when f is a curve a f |[a;b] is a called a subcurve of f .
Two arcs f and g from A to B in a space X are said homotop when there is a continuous function H :

[0; 1] × [0; 1] → X such that H(0, t) = f (t), H(1, t) = g(t), H(s, 0) = f (0) = g(0) and H(s, 1) = f (1) = g(1)
. The relation of being homotop is a relation of equivalence and when two arcs f and g, in a space X, are homotop we shall write f ≈ X g.

For the points A and B, we write P X (A, B) the set of homotopy classes of arcs going from A to B and we write [f ] X for the homotopy class of f . If we define an operation • of concatenation of arcs that, given two arcs f 1 and f 2 , respectively from A to B and B to C, produces an arc

f 1 • f 2 such that f 1 • f 2 (t) = f 1 (2t) when t ≤ 1 2 f 2 (2t -1) when t ≥ 1 2
then, when g 1 and g 2 are respectively homotop to f 1 and f 2 (i.e.

g 1 ∈ [f 1 ] X and g 2 ∈ [f 2 ] X ), we have [g 1 • g 2 ] X = [f 1 • f 2 ] X .
Thus we can interpret concatenation at the level of homotopy classes as an operation

• of type P X (A, B) → P X (B, C) → P X (A, C) such that [f 1 • f 2 ] X = [f 1 ] X • [f 2 ] X .
This operation can be easily be proved to be associative and to have an inverse for every [f ] X , so that the operation • equips the set P X of homotopy classes with the algebraic structure of a groupoid, the fundamental groupoid of X. We shall write π(X) for the fundamental groupoid of X. In particular, when we restrict our attention to homotopy classes to closed curves of base point A, then the sub-groupoid we obtain is actually a group, the fundamental group of X at A. We shall write π(X, A) for the fundamental group of X at A. Given two points A and B of a path connected space X we always have that π(X, A) and π(X, B) are isomorphic groups. In what follows we will always work in path connected spaces, thus for a given space X we will refer to its fundamental group. An arc or a curve f is said trivial when its homotopy class is the neutral element of π(X, f (0)).

The fundamental groupoid of a space X allows expressing particular properties of X that are carried by continuous functions to other spaces. Indeed, given a continuous function ϕ from X to Y , ϕ induces a homomorphism φ between the fundamental groupoids of X and Y because we have:

• whenever g ∈ [f ] X , ϕ • g ∈ [ϕ • f ] Y , • ϕ • (f • g) = (ϕ • f ) • (ϕ • g), thus by defining φ([f ] X ) = [ϕ•f ] Y , we obtain that φ([f ] X •[g] X ) = φ([f •g] X ) = [ϕ • (f • g)] Y = [(ϕ • f ) • (ϕ • g)] Y = [ϕ • f ] Y • [ϕ • g] Y = φ([f ] X ) • φ([g] X )
, which shows that φ is a groupoid homomorphism. Note that if ϕ is a homeomorphism, then φ is a groupoid isomorphism. Furthermore when we consider closed curves of X at base point A, and if ϕ(A) = B then φ is group homomorphism from π(X, A) to π(Y, B) (and a group isomorphism when ϕ is a homeomorphism).

Given X and Y two topological spaces, a continuous function ϕ from X to Y is said to evenly cover an open subset U of Y when ϕ -1 (U ) is the disjoint union open subsets of X, each of the open sets being homeomorphically mapped on U by ϕ. A continuous function from X to Y is a covering projection when for every y in Y there is an open neighborhood of y which is evenly covered by ϕ. When ϕ is a covering projection from X to Y , X is called the covering space and Y is called the base space, moreover ϕ verifies the following properties:

1. Unique path-lifting property: given f an arc of Y , given t in [0; 1] and x in ϕ -1 (f (t)), there is a unique arc g of X such that ϕ • g = f and g(t) = x.

2. Homotopy-lifting property: given f and g two arcs on X such that f (0) = g(0), then whenever

[ϕ • f ] Y = [ϕ • g] Y we have that [f ] X = [g] X
In section 4 we are going to use these notions so as to prove the following Theorem.

Theorem 1 If f is a Jordan curve of C such that f (0) = A and f (t) = D for some t in (0; 1) and there are two points A and D in the interior of f such that D -A = D -A , then there are t 1 and t 2 such that t 1 < t 2 and one of the following properties holds: there are rational transductions transforming one language into the other and vice-versa), and that 2-MCFLs form a full AFL, we only need to prove that O 2 is a 2-MCFL. The equivalence is established by the following Lemma.

1. [t 1 ; t 2 ] ⊆ (0; t) and f (t 2 ) -f (t 1 ) = D -A 2. [t 1 ; t 2 ] ⊆ (t; 1) and f (t 2 ) -f (t 1 ) = A -D 3. M IX
Lemma 1 M IX and O 2 are rationnally equivalent.

Proof. The Lemma is proved using the following rational transductions1 :

1. the rational transduction from O 2 to M IX can be described by taking the rational set R 1 = {a|b|ab} * and the string homomorphism h such that h(a) = a, h(b) = b, h(a) = c and h(b) = . We will see below that M IX = h(O 2 ∩ R 1 ). 2. the rational transduction from M IX to O 2 is obtained by considering the rational set R 2 = {abab|cc|cbcb|aa} * and the homomorphism g such that g(a) = abab, g(a) = cc, g(b) = cbcb g(b) = aa. We will show below that

O 2 = g -1 (M IX ∩ R 2 ).
To prove that the first transduction transforms O 2 into M IX, it suffices to remark that the language O 2 ∩ R 1 is the language of strings that contain the same number of occurrences of a, b and ab. Thus mapping a to a, b to b and ab to c, as the homomorphism h does, gives all the strings contained in M IX.

For showing that the second transduction transforms M IX into O 2 , one needs to remark that a given string w in M IX ∩ R 2 can be split in a unique way into strings v 1 , . . . , v n such that w = v 1 . . . v n and for all i in [n], v i is in {abab; cc; cbcb; aa} and that if we let p 1 , p 2 , p 3 and p 4 be the number of v i that are respectively equal to abab, cc, cbcb and aa, then we have that p 1 + p 4 , p 1 + p 3 , p 2 + p 3 are respectively the number of a, b and c that occur in w. As w is in M IX, we have that the following identity holds:

p 1 + p 4 = p 2 + p 3 = p 1 + p 3
but this identity is equivalent to have p 1 = p 2 and p 3 = p 4 . Thus as w is in M IX, we have obviously g -1 (w) in O 2 . Conversely it is obvious that whenever w is in O 2 , then g(w) is in M IX ∩R 2 so that we indeed have

O 2 = g -1 (M IX ∩R 2 ).
The main argument of the proof that O 2 is a 2-MCFL is of geometric nature. We define an interpretation ϕ(w) of the words of {a; ā; b; b} * in Z + iZ a subset of the complex numbers C:

• ϕ( ) = 0 • ϕ(aw) = ϕ(w) + i and ϕ(āw) = ϕ(w) -i • ϕ(bw) = ϕ(w) + 1 and ϕ( bw) = ϕ(w) -1
Obviously ϕ is a monoid homomorphism and O 2 = ϕ -1 (0) (this is just another way of saying that O 2 is the group language of Z + iZ which is isomorphic to Z 2 ).

Given w in {a; ā; b; b} * such w = c 1 . . . c n with c i in {a; ā; b; b}, we interpret w as the arc C(w) defined by:

C(w)(t) = ntϕ(c 1 ) when t ≤ 1 n ϕ(c 1 . . . c k-1 ) + n(t -k-1 n )ϕ(c k ) when k-1 n < t ≤ k n
Notice that the construction of C(w) implies that every t in [0; 1], either the imaginary or the real part of C(w)(t) is in Z. Furthermore, we have the following fact:

Fact 2. Given t in [0; 1], both the imaginary and parts of C(w

)(t) are in Z iff t = k |w| with 0 ≤ k ≤ |w|, in such a case we obviously have that C(w)(t) = ϕ(v k ) if v k is the left factor of length k of w. Lemma 2 Given z in Z + iZ, a word w and t 1 , t 2 in [0; 1], if C(w)(t 1 ) is not in Z + iZ and C(w)(t 1 ) -C(w)(t 2 ) = z then if k 1 and k 2 are the integers such that k1 |w| ≤ t 1 ≤ k1+1 |w| , and k2 |w| ≤ t 2 ≤ k2+1
|w| , then one of the following properties holds:

1. either C(w)( k1 |w| ) -C(w)( k2 |w| ) = C(w)( k1+1 |w| ) -C(w)( k2+1 |w| ) = z, 2. or C(w)( k1+1 |w| ) -C(w)( k2 |w| ) = C(w)( k1 |w| ) -C(w)( k2+1 |w| ) = z.
Proof. As C(w)(t 1 ) is not in Z + iZ, only the imaginary part or the real part of C(w)(t 1 ) is in Z. Without loss of generality we assume that the real part of C(w)(t 1 ) is in Z (the other case can be treated in a similar way) and that C(w)(t 1 ) = h + i(l + δ) with, h and l in Z and δ in (0; 1). By definition of C we have that one of the following holds:

1. either C(w)( k1 |w| ) = h + il and C(w)( k1+1 |w| ) = h + i(l + 1), 2. or C(w)( k1 |w| ) = h + i(l + 1) and C(w)( k1+1 |w| ) = h + il. Since C(w)(t 1 ) -C(w)(t 2 ) = z we have C(w)(t 2 ) = h + i(l + δ) + z. And as z is in Z + iZ, as previously we must have 1. either C(w)( k2 |w| ) = h + il + z and C(w)( k2+1 |w| ) = h + i(l + 1) + z, 2. or C(w)( k2 |w| ) = h + i(l + 1) + z and C(w)( k2+1 |w| ) = h + il + z, from which the conclusion follows.
Notice also that w is in O 2 if and only if C(w) is a closed curve. It is easy to establish that C(w) satisfies the following properties:

• if w = then C(w)(t) = 0 • if w ∈ {a; a; b; b} then C(w)(1) = ϕ(w) • if w = w 1 w 2 then C(w)(t) = C(w 1 )(t |w1w2| |w1| ) when t < |w1| |w1w2| C(w 2 )(t |w1w2| |w2| -|w1| |w2|
) + ϕ(w 1 ) otherwise An example of an arc representation of a word is given by figure 1, where a black dot is used to mark the starting point and an arrow is giving the starting direction. A word w is said simple if for every element w of F(w)/{ }, ϕ(w ) = 0. Fact 2 implies:

Fact 3. w is a simple word iff C(w) is a simple arc. A subword w of w is a simplification of w when w is simple, w = v 1 . . . v n and w = u 1 v 1 . . . u n v n u n+1 with ϕ(u i ) = 0 for i in [n + 1].
The set of simplifications of w will be written sp(w).

Lemma 3 If w is not in O 2 then sp(w) = ∅.
Proof. We proceed by induction on the size of w.

In case w is simple then w is in sp(w). In case w is not simple, let u be non-trivial factor of w such that ϕ(u) = 0 and w = w 1 uw 2 . Since, w is not in O 2 , w 1 w 2 is also not in O 2 and thus, by induction hypothesis, sp(w 1 w 2 ) is not empty. Let w be in sp(w 1 w 2 ), we are going to see that w is in sp(w). Indeed, since w is in sp(w

1 w 2 ), w = v 1 . . . v n and w 1 w 2 = u 1 v 1 . . . u n v n u n+1 with ϕ(u i ) = 0 for all i in [n + 1]. This implies that: 1. either w 1 = u 1 v 1 . . . u k v l,k and w 2 = v r,k u k+1 . . . v n u n+1 with v k = v l,k v r,k 2. or w 1 = u 1 v 1 . . . v k-1 u l,k and w 2 = u r,k v k . . . u n v n u n+1 with u k = u l,k u r,k
In the first case, we have that w = u 1 v 1 . . . u k v l,k uv r,k . . . u n v n u n+1 and since ϕ(u) = 0 and for all i in [n + 1], ϕ(u i ) = 0, we have that w in sp(w).

In the second case, we have that

w = u 1 v 1 . . . u k u l,k uu r,k v k . . . u n v n u n+1 and since ϕ(u l,k uu r,k ) = ϕ(u) + ϕ(u l,k u r,k ) = 0 and for all i in [n + 1] with i = k we have ϕ(u i ) = 0 we finally obtain that w is in sp(w).
Lemma 4 If w ∈ sp(w) and w = w 1 w 2 with w 1 = and w 2 = then w = w 1 w 2 such that w 1 and w 2 are respectively in sp(w 1 ) and sp(w 2 ).

Proof. If w is in sp(w), then w = u 1 v 1 . . . u n v n u n+1 , w = v 1 . . . v n , and ϕ(u i ) = 0 for all i in [n + 1]. This implies that w 1 = v 1 . . . v k-1 v 1,k and w 2 = v 2,k v k+1 . . . v n for some k in [n] and v k = v 1,k v 2,k . It suffices to choose w 1 = u 1 v 1 . . . v k-1 u k v 1,k and w 2 = v 2,k u k+1 v k+1 . . . u n v n u n+1 . Corollary 1. If w ∈ sp(w) and w = w 1 . . . w n with w i = for all i in [n], then w = w 1 . . . w n such that for all i in [n] w i is in sp(w i ).
Proof. A simple iteration of the preceding Lemma.

We define G = (Ω, {a; a; b; b}, R, S) where Ω = ({S; Inv}, ρ) with ρ(S) = 1 and ρ(Inv) = 2 and where R is made of the rules that have one of the following forms:

1. S(x 1 x 2 ) :-Inv(x 1 , x 2 ), 2. Inv(t 1 , t 2 ) :-Inv(x 1 , x 2 ) where t 1 t 2 ∈ perm(x 1 x 2 aā) ∪ prem(x 1 x 2 b b), 3. Inv(t 1 , t 2 ) :-Inv(x 1 , x 2 ), Inv(y 1 , y 2 ) where t 1 t 2 ∈ prem(x 1 x 2 y 1 y 2 ) 4. Inv( , )
N.B.: the items 2 and 3 represent finite sets of rules. It is easy to see that the language generated by G is included in O 2 . We will see that the converse also holds.

We are going to show the following Lemma about this grammar:

Lemma 5 Whenever w 1 and w 2 are elements of {a; a; b; b} * such that

w 1 w 2 is in O 2 , Inv(w 1 , w 2 ) is derivable in G.
As a consequence we obtain that the language of G is precisely O 2 and thus the expected Theorem.

Theorem 2 M IX and O 2 are 2-MCFLs.

Fact 1 implies the following corollary.

Corollary 2. M IX and O 2 are recognized by a third-order collapsible pushdown automaton.

Proof of Lemma 5. The proof is done by induction on |w

1 w 2 | + max(|w 1 |, |w 2 |).
There are five cases:

Case 1 w 1 and w 2 are in O 2 . In case neither of them is the empty string, we have, by induction hypothesis, that Inv(w 1 , ) and Inv(w 2 , ) are derivable so that Inv(w 1 , w 2 ) is derivable using the rule Inv(x 1 x 2 , y 1 y 2 ) :-Inv(x 1 , x 2 ), Inv(y 1 , y 2 ).

In case either w 1 or w 2 is the empty string then when both of them are equal to the empty string, Inv(w 1 , w 2 ) is obviously derivable using rule 4. In case w 1 or w 2 is not the empty string, without loss of generality, we may assume that w 2 is equal to the empty string and w 1 is not. Then, we have w 1 in O 2 and w 1 = , so that, w 1 has length at least 2 and there is v 1 and v 2 both different from the empty string such that w 1 = v 1 v 2 . So by induction hypothesis Inv(v 1 , v 2 ) is derivable and using the rule Inv(x 1 x 2 , y 1 y 2 ) :-Inv(x 1 , x 2 ), Inv(y 1 , y 2 ) together with the premises Inv(v 1 , v 2 ) and Inv( , ) we obtain a derivation of Inv(v 1 v 2 , ), i.e. a derivation of Inv(w 1 , w 2 ).

Case 2 In case w 1 = s 1 w 1 s 2 , w 2 = s 3 w 2 s 4 so that s 1 s 2 s 3 s 4 ∈ {aa; aa; bb; bb}, then we can conclude by applying one of the rules defined by the item 2 in the definition of G. For example if w 1 = aw 1 a then we let s 1 = a, s 2 = a, s 3 = s 4 = , w 2 = w 2 , and we have s 1 s 2 s 3 s 4 = aa. So by induction hypothesis, Inv(w 1 , w 2 ) is derivable, and we may derive Inv(w 1 , w 2 ) simply by using the rule Inv(ax 1 a, x 2 ) :-Inv(x 1 , x 2 ).

Case 3 Neither w 1 nor w 2 is the empty string and either w 1 or w 2 has a nontrivial left or right factor that is in O 2 . Without loss of generality, we may suppose that w 1 = vw 1 where v is not the empty string and v in O 2 . By induction hypothesis (that can be used since neither v nor w 2 are the empty string) Inv(v, ) and Inv(w 1 , w 2 ) are derivable, and then Inv(w 1 , w 2 ) is derivable using the rule Inv(x 1 y 1 , y 2 x 2 ) :-Inv(x 1 , x 2 ), Inv(y 1 , y 2 ) of the family of rules 3.

Case 4 Neither w 1 nor w 2 is in O 2 and there is w 1 and w 2 respectively in sp(w 1 ) and sp(w 2 ) such that the curves C(w 1 w 2 ) is not a simple curve. From fact 3, we know that C(w 1 ) and C(w 2 ) are simple arcs. Since

C(w 1 w 2 )(t) = C(w 1 )(t |w 1 w 2 | |w 1 | ) when t < |w 1 | |w 1 w 2 | C(w 2 )(t |w 1 w 2 | |w 2 | - |w 1 | |w 2 | ) + ϕ(w 1 ) otherwise
and since C(w 1 ) and C(w 2 ) are simple while C(w 1 w 2 ) is not simple, there must be t 1 and t 2 respectively in (0,

|w 1 | |w 1 w 2 | ) and ( |w 1 | |w 1 w 2 | , 1) such that: C(w 1 w 2 )(t 1 ) = C(w 1 w 2 )(t 2 ) (1)
which can be rephrased as:

C(w 1 )(t 1 |w 1 w 2 | |w 1 | ) = C(w 2 )(t 2 |w 1 w 2 | |w 2 | - |w 1 | |w 2 | ) + ϕ(w 1 ) (2)
Moreover, either the imaginary part or the real part of C(w 1 w 2 )(t 1 ) is in Z.

In case both the imaginary and the real part of C(w

1 w 2 )(t 1 ) = C(w 1 )(t 1 |w 1 w 2 | |w 1 | ) are in Z then, fact 2 implies that t 1 |w 1 w 2 | |w 1 | = k |w 1 | with 0 ≤ k ≤ |w 1 |. But since t 1 is in (0, |w 1 | |w 1 w 2 | ) we must have that 0 < k < |w 1 |. Fact 2 also implies that w 1 = v 1 v 2 with v 1 being the left factor of length k of w 1 and ϕ(v 1 ) = C(w 1 )(t 1 |w 1 w 2 | |w 1 | ).
From the fact that 0 < k < |w 1 |, we have that neither v 1 nor v 2 is the empty string. Similarly 2). Now, Lemma 4, implies that w 1 = v 1 v 2 and w 2 = v 3 v 4 so that v i is in sp(v i ) for all i in [4] and v 1 v 4 and v 2 v 3 are in O 2 and since neither v 1 nor v 2 is the empty string, it is also the case that neither v 1 nor v 2 is the empty string which has the consequence that

w 2 = v 3 v 4 with C(w 2 )(t 2 |w 1 w 2 | |w 2 | - |w 1 | |w 2 | ) = ϕ(v 3 ). But (2) im- plies that ϕ(v 1 ) = ϕ(v 3 ) + ϕ(w 1 ) and, since ϕ(w 1 ) = ϕ(v 1 ) + ϕ(v 2 ), we obtain ϕ(v 2 ) + ϕ(v 3 ) = 0 so that v 2 v 3 is in O 2 . Because w 1 w 2 is in O 2 , w 1 w 2 is also in O 2 and therefore, ϕ(w 2 ) = -ϕ(w 1 ) so that with ϕ(v 1 ) = ϕ(v 3 ) + ϕ(w 1 ) and ϕ(w 2 ) = ϕ(v 3 )+ϕ(v 4 ) we have ϕ(v 1 )+ϕ(v 4 ) = 0 and v 1 v 4 is in O 2 (see figure
|v 1 v 4 | < |w 1 w 2 | and |v 2 v 3 | < |w 1 w 2 |.
Then, by induction hypothesis, Inv(v 1 , v 4 ) and Inv(v 2 , v 3 ) are derivable, which, with the rule Inv(x 1 y 1 , y 2 x 2 ) :-Inv(x 1 , x 2 ), Inv(y 1 , y 2 ), allows us to finally derive Inv(w 1 , w 2 ).

In case only the imaginary or real part of C(w 1 w 2 )(t 1 ) is an integer let k 1 and k 2 be the integer such that k1

|w 1 w 2 | < t 1 < k1+1 |w 1 w 2 | and k2 |w 1 w 2 | < t 2 < k2+1 |w 1 w 2 | . Notice that since t 1 ∈ (0; |w 1 | |w 1 w 2 | ) and t 2 ∈ ( |w 1 | |w 1 w 2 | ; 1), we must have 0 ≤ k 1 < k 1 + 1 ≤ |w 1 | and |w 1 | ≤ k 2 < k 2 + 1 ≤ |w 1 w 2 |. The identity (1), implies that C(w 1 w 2 )(t 1 ) -C(w 1 w 2 )(t 2 ) is in Z + iZ so that Lemma 2 implies that 1. either C(w 1 w 2 )( k1 |w 1 w 2 | ) = C(w 1 w 2 )( k2 |w 1 w 2 | ) and C(w 1 w 2 )( k1+1 |w 1 w 2 | ) = C(w 1 w 2 )( k2+1 |w 1 w 2 | ), v 1 v 2 v 3 v 4 A B w 1 w 2 Figure 2: C(w 1 w 2 ) is not a simple curve (Case 4) 2. or C(w 1 w 2 )( k1 |w 1 w 2 | ) = C(w 1 w 2 )( k2+1 |w 1 w 2 | ) and C(w 1 w 2 )( k1+1 |w 1 w 2 | ) = C(w 1 w 2 )( k2 |w 1 w 2 | ). Which is equivalent to (letting k 2 = k 2 -|w 1 |): 1. either C(w 1 )( k1 |w 1 | ) = C(w 2 )( k 2 |w 2 | ) + ϕ(w 1 ) and C(w 1 )( k1+1 |w 1 | ) = C(w 2 )( k 2 +1 |w 2 | ) + ϕ(w 1 ) 2. or C(w 1 )( k1 |w 1 | ) = C(w 2 )( k 2 +1 |w 2 | ) + ϕ(w 1 ) and C(w 1 )( k1+1 |w 1 | ) = C(w 2 )( k 2 |w 2 | ) + ϕ(w 1 ). Thus, in case either 0 < k 1 < |w 1 |, or 0 < k 1 + 1 < |w 1 |, or 0 < k 2 < |w 2 |, or 0 < k 2 + 1 < |w 2 |, we may conclude as above. Otherwise, k 1 = 0, k 1 + 1 = |w 1 |, k 2 = 0 and k 2 + 1 = |w 2 | which implies that |w 1 | = 1 and |w 2 | = 1.
Thus there are four possibilities: either w 1 = a and w 2 = a, or w 1 = a and w 2 = a, or w 1 = b and w 2 = b, or w 1 = b and w 2 = b. Without loss of generality, we assume that w 1 = a and w 2 = a. As a consequence, w 1 = u 1 au 2 and w 2 = u 3 au 4 with ϕ(u 1 ) = ϕ(u 2 ) = ϕ(u 3 ) = ϕ(u 4 ) = 0, if one of the u i is not the empty string, then the induction works as in case 3, otherwise, if w 1 = w 1 = a and w 2 = w 2 = a, and, similarly to case 2, it suffices to derive Inv(w 1 , w 2 ) (i.e. Inv(a, a)) from Inv( , ) and the rule Inv(ax 1 , ax 2 ) :-Inv(x 1 , x 2 ).

Case 5 The last case is the complement of all the previous cases, w 1 and w 2 verify the following properties:

1. neither w 1 nor w 2 is in O 2 , 2. w 1 and w 2 do not start of end with compatible letters, 3. neither w 1 nor w 2 has a non-trivial left or right factor that belongs to O 2 , 4. if w 1 and w 2 are respectively in sp(w 1 ) and sp(w 2 ), then C(w 1 w 2 ) is a simple curve (i.e. a Jordan curve).

From Lemma 3, because w 1 / ∈ O 2 and w 2 / ∈ O 2 , there are w 1 and w 2 respectively in sp(w 1 ) and sp(w 2 ). By definition it must be that case that w 1 = u 1 v 1 . . . u n v n u n+1 with ϕ(u i ) = 0 for all i in [n + 1] and w 1 = v 1 . . . v n . But as, by hypothesis, w 1 may not have a non-trivial left or right factor in O 2 , we must have u 1 = u n+1 = so that first and last letters of w 1 are the same as the first and last letters of w 1 . Similarly, the same holds for w 2 and w 2 . Because C(w 1 w 2 ) is a Jordan curve, it splits the plane into two components, the interior of the curve and the exterior of the curve, furthermore, while traversing the curve the interior and the exterior are always on the same side of the curve. We call unit square in Z + iZ a set of points of C that lie inside a square whose diagonal is given by z and z + 1 + i with z in Z + iZ. A unit square is adjacent to C(w 1 w 2 ) if one of its corners is on C(w 1 w 2 ). The fact that C(w 1 w 2 ) is a Jordan curve implies that while traversing C(w 1 w 2 ):

1. either the interior every unit square adjacent to C(w 1 w 2 ) appearing on the right of are in the interior of C(w 1 w 2 ) while the interior of the ones appearing on the left are in its exterior, 2. or the converse.

Exploiting this fact, figure 3 shows all the possible cases (omitting the cases that can be obtained by symmetry; in particular it focuses on the cases where the first and last letters of w 1 and w 2 are either a or b), the red arrows represent the starting and ending letters of w 1 while the blue ones represent the starting and ending letters of w 2 and we have materialized with green vectors (resp. yellow vectors) two points that must be either both outside C(w 1 w 2 ) or both inside C(w 1 w 2 ). Moreover when the pair of points defined with the green vectors, are outside the C(w 1 w 2 ), then the points defined with the yellow vectors are inside C(w 1 w 2 ) and conversely (figure 4 exemplifies the two different cases for a particular configuration of the starting and ending letters of w 1 and w 2 ). In that context we can apply Theorem 1 considering that f = C(w 1 w 2 ) is a Jordan curve, that the points A and D of C(w 1 w 2 ) are respectively given by C(w 1 w 2 )(0) and C(w 1 w 2 )(

|w 1 | |w 2 |
) (which are the starting and ending points of the part of C(w 1 w 2 ) that represents w 1 ), the points A and D are respectively either A + z and D + z, or A -z and D -z with z = -1 2 + i 1 2 . Then Theorem 1 gives us t 1 and t 2 such that t 1 < t 2 and such that one of the following statements holds:

1. [t 1 ; t 2 ] ⊆ (0;

|w 1 | |w 2 | ) and f (t 2 ) -f (t 1 ) = D -A 2. [t 1 ; t 2 ] ⊆ ( |w 1 | |w 2 | ; 1) and f (t 2 ) -f (t 1 ) = A -D
We may suppose that the first statement holds (the other case being symmetric) and in order to conclude we need to prove that this gives the existence of some non-empty strings v 1 , v 2 and v 3 such that w 1 = v 1 v 2 v 3 and ϕ(v 2 ) = ϕ(w 1 ). Once this is proved, we have, using Lemma 1, that there are non-empty strings v 1 , v 2 , and v 3 such that w 1 = v 1 v 2 v 3 and ϕ(v 2 ) = ϕ(w 1 ) so that v 1 v 3 and v 2 w 2 are in O 2 and that, by induction hypothesis Inv(v 1 , v 3 ) and Inv(v 2 , w 2 ) are derivable from which, using the rule Inv(x 1 y 1 x 2 , y 2 ) :-Inv(x 1 , x 2 ) Inv(y 1 , y 2 ), we can conclude that Inv(w 1 , w 2 ) is derivable. Proving the existence of v 1 , v 2 and v 3 relies on fact 2. Indeed, once it is proved that there are t 1 and t 2 such that t 1 < t 2 , [t 1 ; t 2 ] ⊆ (0;

|w 1 | |w 2 | ), f (t 2 ) - f (t 1 ) = D -A
and such that f (t 1 ) and f (t 2 ) have both their imaginary and real parts in Z, fact 2 gives us v 1 , v 2 and v 3 . In case both f (t 1 ) and f (t 2 ) are in Z + iZ then we are done simply by choosing t 1 = t 1 and t 2 = t 2 . Otherwise, by construction of D and A, we have that D -A is in Z + iZ. We let k 1 and k 2 be such that:

1. k1 |w 1 | < t 1 |w 1 w 2 | |w 1 | < k1+1 |w 1 | , 2. k2 |w 1 | < t 2 |w 1 w 2 | |w 1 | < k2+1 |w 1 | .
and Lemma 2 implies that:

1. either C(w 1 )( k2 |w 1 | )-C(w 1 )( k1 |w 1 | ) = D-A and C(w 1 )( k2+1 |w 1 | )-C(w 1 )( k1+1 |w 1 | ) = D -A, 2. or C(w 1 )( k2+1 |w 1 | ) -C(w 1 )( k1 |w 1 | ) = D -A and C(w 1 )( k2 |w 1 | ) -C(w 1 )( k1+1 |w 1 | ) = D -A.
In any case, the conclusion follows the choice of t 1 = k1+1 |w 1 w 2 | and the corresponding t 2 ( k2 |w 1 w 2 | or k2+1 |w 1 w 2 | depending on the case).

Well-nestedness

A question that immediately arises from the proof we give that M IX and O 2 are 2-MCFLs is whether the intricacy of case 5 is necessary for proving the result. A thing we can remark is that the four first cases only use rules that are well-nested to make the induction work. Indeed, case 1 is based on the rule:

Inv(x 1 x 2 , y 1 y 2 ) :-Inv(x 1 , x 2 ), Inv(y 1 , y 2 )
Inv(αx 1 ᾱ, x 2 ) :-Inv(x 1 , x 2 ) Inv(x 1 α, ᾱx 2 ) :-Inv(x 1 , x 2 ) Inv(x 1 , αx 2 ᾱ) :-Inv(x 1 , x 2 )
where α is in {a; ā; b; b} and ᾱ = ā, ᾱ = a, ᾱ = b and ᾱ = b when α = a, α = ā, α = b and α = b respectively. Case 3 only requires the rules:

Inv(x 1 x 2 y 1 , y 2 ) :-Inv(x 1 , x 2 ), Inv(y 1 , y 2 ) Inv(y 1 x 1 x 2 , y 2 ) :-Inv(x 1 , x 2 ), Inv(y 1 , y 2 ) Inv(y 1 , x 1 x 2 y 2 ) :-Inv(x 1 , x 2 ), Inv(y 1 , y 2 ) Inv(y 1 , y 2 x 1 x 2 ) :-Inv(x 1 , x 2 ), Inv(y 1 , y 2 )
and that parts of case 4 that are disjoint from case 2 and case 3 only rely on the rules:

Inv(x 1 y 1 , y 2 x 2 ) :-Inv(x 1 , x 2 ), Inv(y 1 , y 2 )
Whereas case 5 uses the rules:

Inv(x 1 y 1 x 2 , y 2 ) :-Inv(x 1 , x 2 ), Inv(y 1 , y 2 ) Inv(x 1 , y 1 x 2 y 2 ) :-Inv(x 1 , x 2 ), Inv(y 1 , y 2 )
The four first cases only rely on well-nested rules while the fifth one relies on non-well-nested rules. We here show an example of word, that is in O 2 but that is not in the language defined by the grammar where the non-well-nested rules have been omitted. This word is:

w = aabbā bābbaaa bbbb āāāb
which is represented by the curve on figure 5. Figure 6 and figure 7 show all the possible ways of one can parse the word w using the grammar where the non-well-nested rules have been removed. We have proceeded in splitting w in all the possible ways into two strings w 1 and w 2 and we have drawn w 1 in red and w 2 in blue. Then we have recursively put arrows between possible premises that would allow to derive these pairs of strings. The only cases that show up in the course of this process are cases 2 and 4. The vast majority of premises are obtained using case 2 with the rules:

Inv(αx 1 ᾱ, x 2 ) :-Inv(x 1 , x 2 ) Inv(x 1 α, ᾱx 2 ) :-Inv(x 1 , x 2 ) Inv(x 1 , αx 2 ᾱ) :-Inv(x 1 , x 2 )
There are cases where both case 2 and case 4 can apply, but, in those cases, without loss of generality we may simply apply case 2. The only case where only case 4 applies, without possibly using rules of case 2, is that of the pair:

(abbā bābba, bbb )

which is surrounded with a purple line in figure 7. Its premises may be the pairs (abbā b, b) and (ābba, bb ) surrounded with a yellow line, and the pairs (abbā, bb ) and ( bābba, b), surrounded with a green line. For all the splitting of w in w 1 and w 2 , using the well-nested rules, we cannot obtain a derivation of Inv(w 1 , w 2 ). In each case a derivation cannot be completed because it involves a pair of strings for which only case 5 can apply. This shows that the non-well-nested rules are mandatory in order to make the grammar capture O 2 . We believe that this situation can be generalized so as to prove that there is no well-nested 2-MCFL (i.e. no Tree Adjoining Language) that can define O 2 . Hopefully yet another generalisation would allow to prove that O 2 is not a well-nested MCFL.

A Theorem on Jordan curves

In this section we give the proof of Theorem 1. This Theorem is actually stronger than necessary to obtain Theorem 2. We could have taken advantage from the fact that the curves we are interested in are drawn on the grid. But we have preferred to prove a theorem that presents an interest on its own. The drawback of this generality is that it makes certain parts of the proof get slightly more complicated.

For proving Theorem 1, we shall assume, without loss of generality, that A = 0 and D = 1, and D -A = 1. The idea behind the proof is to use the complex exponential function (i.e. exp : z → e 2iπz ) so as to observe certain properties of curves and arcs in the plane. A first simple property (Theorem 5) is that if a Jordan curve f has k elements of Z in its interior then its image through the exponential is winding k times or -k times (depending on the orientation of f with respect to the chosen orientation of the plane) around 1 (note that for every k in Z, exp(k) = 1). This implies (Corollary 4) in particular that the image by exp of the curve we consider in Theorem 1 is winding at least 2 times or at most -2 times around 1. A second property (Theorem 4) is that for a given Jordan arc f such that f (0) -f (1) = 1 (resp. f (0) -f (1) = -1) the following properties are equivalent:

1. f does not contain any strict (i.e. different from f ) subarc g such that g(0) -g(1) = 1 (resp. g(0) -g(1) = -1) 2. the image of f by exp is a Jordan curve which is winding 1 (resp. -1) time around 0.

As a consequence a Jordan arc f such that f (0) -f (1) = 1 (resp. f (0) -f (1) = -1) which does not contain any strict subarc g such that g(0) -g(1) = 1 (resp. g(0) -g(1) = -1) is transformed by exp into a Jordan curve that winds 0 or 1 (resp. 0 or -1) time around 1. Thus, this second property implies that a Jordan curve that does not satisfy the conclusion of Theorem 1 is a Jordan curve that is composed by an arc f 1 and an arc f 2 such that their respective images by exp are winding 0 or 1 time and 0 or -1 around 1 which implies that the image of f is winding between -1 and 1 time around 1. So that f is contradicting the conclusion of Corollary 4 and therefore cannot satisfy the hypotheses of Theorem 1. From these facts Theorem 1 follows.

Most of the effort of the proof is dedicated to establishing the second property (Theorem 4). The difficulty of the proof is coming more particularly from Lemma 16 which shows the rather intuitive property that a closed curve f winding strictly more than once around a point p contains a subcurve that winds precisely once around p. The proof of Lemma 16 relies on a simple property of Jordan curves (Theorem 6), namely that a Jordan curve f winds 1 time around all the points in its interior or -1 time. The structure of the proof of this Lemma is rather simple: it consists in removing the trivial subcurves of f using an homotopy that only affects those subcurves, then we remove the subcurves of f that are winding negatively around p. In doing so, we obtain a curve g that winds more than f around p, so that, by Lemma 6, it cannot be a Jordan curve, furthermore, by construction, all subcurves of g wind strictly positively around p. There is a natural partial order of inclusion on the subcurves of g and we take a subcurve of g that is minimal for this inclusion relation. As this subcurve is minimal, it must be a Jordan curve and as it is winding positively around p, it must, by Lemma 6, wind only once around it. Then it can be easily checked that this subcurve of g induces a subcurve of f that winds exactly once around p. Most of the technicalities we develop in the course of the proof of Theorem 1 is meant to give a precise meaning to the removal of trivial subcurves or subcurves winding negatively around p. Indeed these removals can be performed in many ways and in certain cases there is an uncountable number of ways of doing it and the number of trivial subcurves we may need to remove can be infinite.

The formalisation of these removals is based on the representation of subcurves as families of closed intervals included in [0; 1]. We concentrate on their crucial property of being what we call transitive systems of closed intervals (Definition 2). We prove Lemma 12 which shows that we may extract from these families a subfamily that allows us to perform the removal. Because we deal with families that are a priori infinite the proof Lemma 12 heavily uses Zorn Lemma. Once we have obtained a family of trivial subcurves whose removal removes all the trivial subcurves, we homotop each of them to a constant curve (i.e. to the curve that is constantly equal to their base point). Thus the curve we obtain is piecewise stationary and in order to complete the removal we need to make it non-stationary. Here, a technicality, that mostly comes from the generality in which we wish to prove Theorem 1, shows up. It comes from the fact that the family of intervals on which the curve is stationary can be infinite. A quite pathological case can be that the cumulated measure (in Lebesgues sense) of the intervals composing this family is 1 (i.e. the measure of [0; 1]!) meaning that the curve is stationary almost everywhere. As the situation is quite similar to Cantor function (see [START_REF] Gelbaum | Theorems and Counterexamples in Mathematics[END_REF]), we use a construction (see Lemma 14) similar to the one of Cantor function in order to make the curve non-stationary. This overall construction has the nice property that every subarc of the curve we obtain is homotop to a subarc of the original curve (this is formalized through the notion of conservative deformation introduce in Definition 3). Then we just need to find a subcurve of this new curve that winds only once around p. As we previously explained, this is done by removing the subcurves that wind negatively around p and taking a minimal subcurve of that new curve that winds positively around p. This minimal subcurve must be a Jordan curve and therefore must wind only once around p. To understand why this subcruve induces a subcurve winding once in the original curve, it suffices to remark that the only way it would not would be that, in the original curve, it was containing a subcurve winding negatively around p. But this would imply that in the original curve it would have been winding negatively around p so that it should have been removed in the process of obtaining the new curve from the original one which leads to a contradiction.

The exposition of the proof is organized as follows. In the subsection 4.1 we present the topological spaces, the mapping between them and the basic properties we are going to use in the proof. In 4.2 we focus more particularly on the punctured plane. We explain the relationship between its fundamental group and winding numbers and we give some basic properties about homotopy classes in term of winding numbers. Subsection 4.3 gives the tools that are necessary to proceed to the removal in a curve of its trivial subcurves or of its subcurves that wind negatively around a point. Because we represent subcurves as intervals this subsection mainly deals with properties of families intervals. The subsection 4.4 contains the proof of Lemma 16. And finally, 4.5 gives the proof of Theorem 1.

Spaces, continuous functions and homomorphisms

We present here the spaces which we are going to use in the proof of Theorem 1. These spaces and their fundamental groups are:

• the plane (we confuse the plane with the field of complex numbers) C whose fundamental group is trivial,

• the punctured plane C p at p: C -{p} whose fundamental group is isomorphic to Z,

• the twice punctured plane C p1,p2 at p 1 , p 2 : C-{p 1 ; p 2 } whose fundamental group is isomorphic to the free group generated by two elements,

• the discretely punctured plane C Z : C -Z whose fundamental group is isomorphic to the free group generated by Z.

For any point z 1 , z 2 and z 3 respectively in C p , C p1,p2 and C Z , we shall identify π(z 0 , C p ) with Z, π(z 1 , C p1,p2 ) with the free group generated by β 1 and β 2 , and π(z 2 , C Z ) with the free group generated by the set {α k | k ∈ Z}. Figure 8 shows the closed curves we choose to be the representatives of the homotopy classes corresponding to the generators of the fundamental groups of the topological spaces under consideration. With these conventions, we have the following properties:

p z 1 1 p 1 z 2 p 2 β 1 β 2 z 3 -1 0 k -1 k α -1 α 0 α k-1 α k C p C p1,p2 C Z
1. Let ι k : C Z → C k (with k ∈ Z) be the inclusion mapping from C Z to C k .
We have that ιk (α i ) = 1 when i = k 0 otherwise 2. Let ρ k : C p1,p2 → C p k , with k in {1; 2}, be the inclusion mapping from C p1,p2 to C p k . We have that ρk (β j ) = 1 when k = j 0 otherwise 22 3. Let exp p :

C → C p z → e 2iπz + p . When f is a curve from A to B we have B -A = k with k ∈ Z if and only if exp p • f is a closed curve and, exp p ([f ] C ) = k. 4. Let exp p : C Z → C 0,1 z → e 2iπz + p . We have that exp p (α k ) = β j 1 β 2 β -j
1 , where j is the integer part of the real part of k -z 3 (z 3 being the base point we have fixed for C Z ).

The properties numbered 1, 2 and 4 are obtained by computing the homotopy classes of the images obtained respectively with ι k , ρ k and exp p of the curves that we have chosen as representatives for the various spaces. For the property numbered 3, the if part is done similarly to the other properties; it suffices to compute the homotopy class of the image by exp p of the line joining A to B which is obviously k. For the only if part, we need to notice that exp p is covering projection (if suffices to remark that for every z ∈ R, exp is an homeomorphism from D z = {x + iy | z ≤ x < z + 1 ∧ y ∈ R} to C 0 ), and use the homotopy lifting property which allows reducing the problem to the computation of the homotopy classes of the circle passing through z 1 (the base point we fixed in C p ) and centered in p, that are simply the lines from z to z + 1 with z in exp -1 p (z 1 ) (notice that z + 1 is also in exp -1 p (z 1 )).

Fundamental group of C p , winding number and Jordan curves

In the punctured plane C p , fixing an orientation of the plane2 , a closed curve f with base point A is associated a winding number k when, according to the orientation, it winds k times around p. A rigorous definition of the winding number, also called the index, is given in [START_REF] Ahlfors | Riemann Surfaces[END_REF].

An easy Theorem (for a proof see [START_REF] Ahlfors | Riemann Surfaces[END_REF]) that correlates the winding number and homotopy classes of the punctured plane is that two curves in the punctured plane are homotop to each other if and only if they have the same winding number.

Theorem 3 Given f and g two curves in the punctured plane C p having the same base point, then the two following properties hold:

1. [f ] Cp = [g] Cp if
and only if f and g have the same winding number, 2. the winding number of f • g is the sum of the winding numbers of f and of g.

This Theorem has the consequence that the homotopy classes of the punctured plane can be faithfully represented as the winding number of the curves. In the following we will often use the notion of winding numbers instead of the homotopy classes for closed curves in the punctured plane.

A Jordan curve splits the plane in two disconnected parts, one being bounded and the other being unbounded. The bounded part is called the interior of the curve and the unbounded one is called the exterior of the curve. And the following Lemma is a consequence of the Theorem 10E of [START_REF] Ahlfors | Riemann Surfaces[END_REF].

Lemma 6 Given a Jordan curve f of C, there is k ∈ {-1; 1} such that for any p of C we have:

1. if p is in the interior of f then [f ] Cp = k 2. if p is in the exterior of f then [f ] Cp = 0
The Lemma says that a Jordan curve is winding one time around each points of its interior positively or negatively depending on its orientation and that also it is not winding (or winding zero time) around any points of its exterior.

Lemma 7 Given a closed curve f in C p then the winding number of f is the same as the winding number of f

|[t;1] • f |[0;t] for every t in [0; 1].
The previous Lemma shows that the winding number of a closed curve in the punctured plane does not depend on the base point.

Lemma 8 Given a closed curve f in C p , such that f |[t1;t2] is also closed then [f ] Cp = [f |[0;t1] • f |[t2;1] ] Cp + [f |[t1;t2] ] Cp .
Proof. From Lemma 7 we have that f has the same winding number as

f |[t1;1] • f |[0;t1] which is homotop to f |[t1;t2] • f |[t2;1] • f |[0;t1] and thus [f ] Cp = [f |[t1;t2] ] Cp + [f |[t2;1] •f |[0;t1] ] Cp . But still using Lemma 7 we have obtain that [f |[t2;1] •f |[0;t1] ] Cp = [f |[0;t1] • f |[t2;1]
] Cp and the result follows.

Lemma 9 Given a closed curve f in C p , and a finite family of intervals

C = {[t 1,1 ; t 2,1 ]; . . . ; [t 1,n ; t 2,n ]} such that t 2,k < t 1,k+1 and f |[t 1,k ;t 2,k ] is also a closed curve, then [f ] Cp = [f |[0;t1,1] • . . . f |[t 2,k ;t 1,k+1 ] • f |[t2,n;1] ] Cp + n k=1 [f |[t 1,k ;t 2,k ] ] Cp .
Proof. This is obtained by a simple inductive use of Lemma 8.

On sets of closed subsets of [0; 1]

This section is devoted to some rather technical matter which aims at studying the distribution of subcurves of a given curves. As subcurves are represented a restriction of arcs/curves to closed intervals of [0; 1], this is the reason why it boils down to the study of properties of sets of closed subsets of [0; 1]. This part of our proof would not be necessary, in the context of only proving the Theorem 1 for curves of the form C(w) with w in O 2 .

Lemma 10 If C is a set of pairwise disjoint non-trivial closed intervals of [0; 1] then, C is countable.
Proof. Because the intervals C are pairwise disjoint and included in [0; 1], there are finitely many of them with a length greater than 1 n for every n in N -{0}. Furthermore, because none of them is trivial, for each C in C, there is n in N such that the length of C is greater than 1 n , from which we can infer that C is countable.

Definition 1. Given a totally ordered set K, (C k ) k∈K is an increasing (resp. decreasing) chain of closed intervals of

[0; 1], if, for k 1 and k 2 in K, k 1 < k 2 implies C k1 ⊆ C k2 (C k2 ⊆ C k1 ). The limit of (C k ) k∈K is the smallest closed interval of [0; 1] that contains k∈K C k (resp. is k∈K C k ).
Lemma 11 Given a totally ordered set K, (C k ) k∈K an increasing chain of closed intervals of [0; 1] and J a subset of [0; 1] such that for every

k in K, C k ∩ J = ∅, if C = [a; b] is the limit of (C k ) k∈K then C k ∩ J is included in {a; b}. Definition 2. A transitive system of closed intervals of [0; 1], C, is a set of non-trivial closed intervals of [0; 1] such that: 1. if C 1 ∩ C 2 = {a} for some a in [0; 1], C 1 ∪ C 2 is in C, 2.
for any increasing chain in C, its limit is in C.

Lemma 12 Given, C, a transitive system of non-trivial closed intervals of [0; 1], there is a countable subset C of C satisfying the following properties:

1. the elements of C are pairwise disjoint, 2. for any C in C there is C in C such that C ∩ C = ∅, and if C ⊆ C then C = C.
Proof. Given D a subset of C we say that D verifies the property P (which we write P(D)) if:

1. the elements of D are pairwise disjoint, 2. for C in C either for every

D ∈ D, C ∩ D = ∅, or there is D in D such that C ∩ D = ∅ and if D ⊆ C then D = C.
Because, C is a transitive system of closed intervals, each of its increasing chain has an upper bound in C. This has the consequence, by Zorn Lemma, that there is a M in C such that M is maximal for the inclusion in C. Thus the set {M } satisfies the property P: the first condition is trivially fulfilled because {M } is a singleton set and the second condition is a consequence of the maximality of M . This shows that there are subsets of C satisfying P.

Let G be a totally ordered set, and (D g ) g∈G be an increasing chain of subsets of C that satisfy P. We are going to see that D = g∈G D g is a subset of C that satisfies P. Let's suppose that there are D 1 and D 2 in D such that D 1 ∩ D 2 = ∅, then let g 1 and g 2 in G be such that D 1 ∈ D g1 and D 2 is in D g2 . If g is the maximum value in G between g 1 and g 2 , then, because the chain (D g ) g∈G is increasing, we have that both D 1 and D 2 are in D g , and as P(D g ) holds, we have that

D 1 = D 2 . Let C in C be such that there is D in D such that C ∩ D = ∅. We let g in G be such that D ∈ D g , since P(D g ) and C ∩ D = ∅, there is D in D g such that D ∩ C = ∅ and if D ⊆ C then D = C. As D is in D g ,
and thus in D, this completes the proof that P(D) holds. Thus any increasing chains of subsets of C satisfying P has an upper bound that satisfies P. Using Zorn Lemma, we let C be a maximal subset of C satisfying P.

We are now going to prove that the family C satisfies the conditions required by the Lemma. The first condition is verified simply because, C verifies P. In order to verify the second condition, it suffices to show that for any C in C, there is C in C such that C ∩ C = ∅. We proceed by contradiction, let's assume that there is C in C such that for any C in C , C ∩ C = ∅. We say that an element D of C has property Q when:

1. C ⊆ D, 2. for every C in C , D ∩ C = ∅
In case any increasing chain of intervals of C verifying Q has an upper bound, Zorn Lemma gives an interval D that is maximum for the inclusion and that satisfies Q. We let D = C ∪ {D} and we verify that P(D) contradicting the maximality of C . Indeed, by construction the intervals of D are pairwise disjoint, and let E in C be such that such that

E ∩ F ∈D F = ∅. In case there is F is in C such that F ∩ E = ∅, because C verifies P, we have the existence of F in C such that E ∩ F = ∅ and E ⊆ F implies F = E. In case for each C in C , E ∩ C = ∅, as E ∩ F ∈D F = ∅, we must have D ∩ E = ∅ and if D ⊆ E, then E verifies Q and the maximality of D implies E = D.
In case there is an increasing chain of intervals of C verifying Q which does not have an upper bound satisfying Q, we let E = [a; b] be its limit (with a ≤ b). In any case we have seen that the supposition that there is a C in C such that C ∩ C ∈C C = ∅ leads to a contradiction. This finally shows that C is a subset of C satisfying the required conditions (the countability of C is just a consequence of Lemma 10).

Lemma 13 Given an arc f in C p , we let:

1. Z f be the set of closed intervals [t 1 ; t 2 ] ⊆ [0; 1] such that t 1 < t 2 , f (t 1 ) = f (t 2 ) and [f |[t1;t2] ] Cp = 0, 2. N f be the set of closed intervals [t 1 ; t 2 ] ⊆ [0; 1] such that f (t 1 ) = f (t 2 ), [f |[t1;t2] ] Cp < 0, 3. P f be the set of closed intervals [t 1 ; t 2 ] ⊆ [0; 1] such that f (t 1 ) = f (t 2 ), [f |[t1;t2] ] Cp > 0.
Z f , N f and P f are transitive systems of closed intervals.

Proof. We are only going to show that Z f is a transitive system of closed intervals,, the proofs concerning N f and P f are essentially the same. By definition, Z f contains no trivial intervals. If [t 1 ; t 2 ] and [t 2 ; t 3 ] with t 1 < t 2 < t 3 are in

Z f then [f |[t1;t3] ] Cp = [f |[t1;t2] ] Cp + [f |[t2;t3] ] Cp = 0 which implies that [t 1 ; t 3 ] is also in Z f .
We finally show that the limit of any increasing chain of Z f is in Z f . Given such a chain ([t 1,k ; t 2,k ]) k∈K where K is a totally ordered set and t 1;k < t 2,k . Thus, the sequences (t 1,k ) k∈K and (t 2,k ) k∈K are respectively decreasing and bounded below by 0, and increasing and bounded above by 1, we define t 1 as inf((t 1,k ) k∈K ) and t 2 as sup((t 2,k ) k∈K ) so that the limit of ([t 1,k ; t 2,k ]) k∈K is [t 1 ; t 2 ]. We have seen (section 4.1) that exp p : C → C p that we define as exp p (z) = exp(z) + p is a covering projection so that for every arc g in C, [exp p • g] Cp = 0 iff g(0) = g(1). We let g be a path of

C such that f = exp p • g. Given k in K, since [f |[t 1,k ;t 2,k ]
] Cp = 0, we have that g(t 1,k ) = g(t 2,k ). So if we let ϕ(x, y) = g(x) -g(y), ϕ is a continuous function from [0; 1] 2 to C and as for all k we have ϕ(t 1,k , t 2,k ) = 0, the continuity of ϕ implies that ϕ(t 1 , t 2 ) = 0. Therefore g(t 1 ) = g(t 2 ) and [f |[t1;t2] ] Cp = 0 which implies that [t 1 ; t 2 ] is in Z f . Lemma 14 Given a set of pairwise disjoint non-trivial closed intervals of [0; 1], C, such that C∈C C = [0; 1], there is a continuous and increasing function, ϕ, from [0; 1] to [0; 1] such that:

1. ϕ(0) = 0 and ϕ(1) = 1, 2. ϕ is constant on each C in C 3. if ϕ is constant on an open interval U then there is C in C such that U ⊆ C.
Proof. From Lemma 10, C is countable. The case where C is finite is easy, it suffices to define ϕ as a piecewise linear function that is constant on each interval C i . In that case the fact that C∈C C = [0; 1] allows satisfying the constraint that ϕ(0) = 0 and ϕ(1) = 1, because C∈C C = [0; 1]. So in case C is infinite, because it is countable, we can index its elements with natural numbers and obtain a family of non-trivial closed intervals (C n ) n∈N such that C in C if and only if there is a unique n in N verifying C = C n . Our construction is similar to the one of the Cantor function (see [START_REF] Gelbaum | Theorems and Counterexamples in Mathematics[END_REF]). We shall define a family of open intervals (I w ) w∈L where L is a subset of {0; 1} * . Let k 1 and k 2 be such that C k1 = [0; a] for some a in [0; 1] and C k2 = [b; 1] and let F 1 = C k1 and F 2 = C k2 . In case there is no such k 1 we let F 1 = [0; 0] and similarly if there is no such k 2 we let F 2 = [1; 1]. We then let I = [0; 1]-(F 1 ∪F 2 ), notice that I cannot be empty because, j∈J C j = [0; 1]. If I w is defined, let k w be the smallest element of N such that C kw is included in I w , if such a k w does not exist then for all v ∈ {0; 1} + , wv is not in L; but if such a k w exists then w0 and w1 are in L and if I w = (a Iw ; b Iw ) and C kw = [a kw ; b kw ], then I w0 = (a Iw ; a kw ) and I w1 = (b kw ; b Iw ). Note that I w0 ∪ I w1 = I w -C k , that whenever w is in L, all the left factors of w are in L and that w0 is in L if and only if is w1 is in L. A simple induction gives that if w and wv are in L then I wv ⊆ I w and that the inclusion is strict when v is not the empty string. Similarly, we obtain that if w 1 and w 2 are both in L and that neither w 1 is a left factor of w 2 nor w 2 is a left factor of w 1 then I w1 ∩ I w2 = ∅. Finally note that for each n in N (provided n = k 1 and n = k 2 in case either k 1 or k 2 exist), there is w such that k w = n.

We are now going to define a sequence of sets (U n ) n∈N such that n∈N U n = [0; 1] -n∈N C n . Given n in N, we define L n to be the set of strings in L which have length n. We then inductively (U n ) n∈N by U 0 = [0; 1] and U n+1 = U n -w∈Ln C kw . Thus U n+1 ⊆ U n and it is quite easy to prove that n∈N U n = [0; 1] -n∈N C n .

Finally we define (ϕ n ) n∈N to be a sequence of piecewise linear increasing and continuous functions from [0; 1] to [0; 1]. More precisely ϕ n is linear and strictly increasing on each connected component of U n (i.e. on each I w such that w ∈ L n ) and constant on [0; 1] -U n . We let ϕ 0 be the piecewise linear function that is constant outside U 0 and such that ϕ 0 (0) = 0 and ϕ 1 (1) = 1. The function ϕ n+1 is the function that is equal to ϕ n on [0; 1] -w∈L n I w and for every w in L n we define the restriction of ϕ n+1 to [a Iw ; b Iw ] as follows (see figure 9): A simple induction on n shows that ϕ n has the expected properties and that for each w ∈ L such that |w| = n, then ϕ n (b Iw ) -ϕ n (a Iw ) = 2 -n which implies that sup t∈[0;1] (|ϕ n+1 (t) -ϕ n (t)|) ≤ 2 -n-1 (see figure 9). Thus the sequence of continuous functions (ϕ n ) n∈N is uniformly convergent and we let ϕ be the continuous function that is the limit of this sequence. Since for all n in N, ϕ n is an increasing function from [0; 1] to [0; 1] such that ϕ n (0) = 0 and ϕ n (1) = 1 and that is constant exactly on the interval C kw with w in L n , and since n∈N = w∈Ln C kw = n∈N C n we have that ϕ, is an increasing continuous function from [0; 1] to [0; 1] that is constant exactly on the intervals of the family (C n ) n∈N and such that ϕ(0) = 0 and ϕ(1) = 1, which is precisely what we were expecting.

Subcurves of curves in C p

In this section, we prove the a technical Lemma that contains most of the difficulties of the proof of Theorem 1.

Before proving the Lemma, we need to prove a technical property that generalizes to arcs in the plane the Corollary 1. This generalization is not trivial at all, since the developments of section 4.3 have been made mostly on the purpose proving it. But before generalizing the result, we first need to extend the Definition 3. An homotopy H that transforms f into g in a space X is said conservative when for every t 1 , t 2 in [0; 1] such that there is t 1 and t 2 in [0

; 1] such that g |[t1;t2] ≈ X f |[t 1 ;t 2 ]
. Then, g is said to be a conservative deformation of f , which we write g ≺ X f

Obviously if f 3 ≺ X f 2 and f 2 ≺ X f 1 then f 1 then f 3 ≺ X f 1 . The relation ≺ X is a partial order inside homotopy classes.

We now prove the generalization of Corollary 1 for arcs.

Lemma 15 Given a non-trivial arc f , there is an arc g such that g ≺ X f and g has no trivial subcurve.

Proof. The proof is done in two steps. We first homotop f so that we obtain an arc h with the property that h ≺ X f and whenever h |[t1;t2] is a trivial subcurve of h, then h is constant on [t 1 ; t 2 ]. We then construct an arc g from h using a conservative homotopy that removes the interval where h is stationary.

From Lemma 13 we have that Z f is a transitive system of closed intervals, Lemma 12 implies that there is a family (C j ) j∈J such that: 1. J is countable and for every j ∈ J, C j ∈ Z f , 2. given j 1 and j

2 in J, C j1 ∩ C j2 = ∅ iff j 1 = j 2 , 3. for every C in Z f , there is j in J such that C ∩ C j = ∅ and C j ⊆ C implies C j = C, 4. j∈J C j = [0; 1] (because f is non-trivial).
Given j in J, since [f |Cj ] Cp = 0, f |Cj can be homotoped to a trivial curve f j such that f j (t) = f |Cj (0) for all t in [0; 1]. We write H j (s)(t) an homotopy G is obviously continuous and we have:

G(s, 0) = g(st 1 + (1 -s)ϕ(t 1 )) = g(st 1 + (1 -s)t 1 ) = g(t 1 ) (5) and G(s, 1) = g(st 2 + (1 -s)ϕ(t 2 )) = g(st 2 + (1 -s)t 2 ) = g(t 2 ) (6)
and, using (4) again,

G(0, t) = g(ϕ(tt 1 + (1 -t)t 2 )) = h(tt 1 + (1 -t)t 2 ) = h |[t 1 ;t 2 ] (7)
and

G(1, t) = g(tt 1 + (1 -t)t 2 ) = g |[t1;t2] (8)
The identities (5), ( 6), ( 7) and ( 8 ] Cp = 0, then t 1 = t 2 . Given such t 1 and t 2 , let t 1 and t 2 be such that ϕ(t 1 ) = t 1 and ϕ(t 2 ) = t 2 . We have seen above that in such a case g

|[t1;t2] ≈ Cp h |[t 1 ;t 2 ] which implies that [h |[t 1 ;t 2 ] ] Cp = 0 and that h is constant on [t 1 ; t 2 ] which implies that t 1 ∼ t 2 and t 1 = t 2 . But, t 1 = ϕ(t 1 ) and t 2 = ϕ(t 2 ) so that, with (3), ψ -1 (t 1 ) = ψ -1 (ϕ(t 1 )) = t 1 = t 2 = ψ -1 (ϕ(t 2 )) = ψ -1 (t 2
) which finally gives t 1 = t 2 because ψ is a homeomorphism. This implies that g has no trivial subcurve.

The following Lemma plays a key role in the proof of Theorem 1. It can be interpreted as a kind of intermediate value Theorem for arcs in the plane. Indeed, as it says that when a closed curve f is doing k turns, with k > 1, around around p in the punctured plane C p , then there is a subcurve of f that is doing exactly one turn around p in C p . As the mapping ϕ from C to C p such that ϕ(z) = e 2iπz/v + p is a covering projection, using the unique path-lifting property, we have that f can be seen as the image of a unique (modulo the choice of g(0) in ϕ -1 (f (0))) curve g such that g(1) -g(0) = kv . What is implied by the Lemma is that there is a subarc h of g such that h(1) -h(0) = v. However, it is not the case that for every natural number l ≤ k there is a subarc h l of g such that h l (1) -h l (0) = lv. For a word w in {a; a; b; b}, this Lemma, together with Fact 2 implies that if ϕ(w) = kz with k in N -{0}, then there is a u, a factor of w, such that ϕ(u) = z.

Lemma 16 Given a closed curve f in C p whose winding number is k such that k > 1 (resp. k < -1), then there is

t 1 , t 2 in [0; 1] such that, t 1 < t 2 , [t 1 ; t 2 ] [0; 1], and f |[t1;t2] is a closed curve whose winding number is 1 (resp. -1).
Proof. We will only study the case where k > 1, the case where k < -1 being symmetric.

From Lemma 15 we have g such that g ≺ Cp f and g contains no trivial subcurves. Recall that N g is the set {[t 1 ; t 2 ] | [g |[t1;t2] ] |Cp < 0}; Lemmas 13 and 12 imply that there is a countable subset N of N g which is a transitive system of closed intervals such that: to the previous Lemma, we have the existence of u 1 and u 2 in [t 1 ; t 2 ] such that u 1 < u 2 and f |[u1;u2] has winding number -1. Then we can see that

f = f |[0;u1] • f |[u1;u2] • f |[u2;1] . By hypothesis, we have that [f ] Cp = [f |[0;u1] • f |[u1;u2] • f |[u2;1] ] Cp = [f |[0;u1] ] Cp + [f |[u1;u2] ] Cp + [f |[u2;1] ] Cp = 1 but h = f |[0;u1] • f |[u2;1] is a closed curve and, since [f |[u1;u2] ] Cp = -1, we have [h] Cp = 2.
This means, using the previous Lemma, that there is v 1 , v 2 in [0; 1] such that v 1 < v 2 and h |[v1;v2] has winding number 1. There are three cases (c.f. figure 10):

1. h ≈ Cp f |[0;v 1 ] • f |[v 1 ;v 2 ] • f |[v 2 ;u1] • f |[u2;1] with h |[v1;v2]] ≈ Cp f |[v 1 ;v 2 ] and the conclusion follows easily, 2. h ≈ Cp f |[0;u1] • f |[u2;v 1 ] • f |[v 1 ;v 2 ] • f |[v 2 ;1] with h |[v1;v2]] ≈ Cp f |[v 1 ;v 2 ]
and, here again the conclusion follows easily,

3. h ≈ Cp f |[0;v 1 ] • f |[v 1 ;u1] • f |[u2;v 2 ] • f |[v 2 ;1] with h |[v1;v2]] ≈ Cp f |[v 1 ;u1] • f |[v 2 ;u 2 ]
but in that case we have 1. f is a simple arc of the plane from a point A to a point B such that B -A = 1 (resp. -1) and there is not t 1 , t 2 such that t 1 < t 2 , [t 1 ; t 2 ] [0; 1] and f (t 2 ) -f (t 1 ) = 1 (resp. f (t 2 ) -f (t 1 ) = -1). 2. exp • f is a Jordan curve in C 0 whose winding number is 1 (resp. -1).

[f |[v 1 ;v 2 ] ] Cp = [f |[v 1 ;u1] • f |[u1;u2] • f |[u2;v 2 ] ] Cp = [f |[v 1 ;u1] • f |[u2;v 2 ] ] Cp + [f |[u1;u2] ] Cp = [h |[v1;v2] ] Cp + [f |[u1;u2] ] Cp = 0 f (0) p f (u 1 ) f (0) p f (u 1 ) h(v 1 ) and h(v 2 ) are on f |[0;u1] h(v 1 ) and h(v 2 ) are on f |[u2;1] f (0) p f (u 1 ) f (0) p f (u 1 ) h(v
Proof. We only treat the case where B -A = 1, the other case being symmetric.

Let g be the curve exp • f . Clearly g must have winding number 1, and, from Corollary 3, there are v 1 and v 2 such that v 1 < v 2 , [v 1 ; v 2 ] [0; 1] and g(v 1 ) = g(v 2 ) if and only if it there are t 1 and t 2 such that t 1 < t 2 , [t 1 ; t 2 ] [0; 1] and g |[t1;t2] has 0 or 1 as winding number. In case g |[t1;t2] has winding number 0 then f (t 1 ) = f (t 2 ) and f is not simple. In case g |[t1;t2] has winding number 1, f (t 2 ) -f (t 1 ) = 1. Thus if g is not simple, f is either not simple or there are t 1 and t 2 such that t 1 < t 2 , [t 1 ; t 2 ] [0; 1] and f (t 2 ) -f (t 1 ) = 1.

Conversely, if f is not simple or if there are t 1 and t 2 such that t 1 < t 2 , [t 1 ; t 2 ] [0; 1] and f (t 2 ) -f (t 1 ) = 1 then clearly g cannot be simple.

In what follows ρ 1 is the inclusion mapping from C 0,1 into C 0 while ρ 2 is the inclusion mapping from C 0,1 into C 1 . where |w| α k is the number of occurrences in w of α k . We also have that

ι k ([f ] C Z ) = ι k (w) = |w| α k -|w| α -1 k
. But in C k . Then, from Lemma 6, we have that either for every k, ι k ([f ] P Z ) belongs to {0; 1} or for every k, ι k ([f ] C Z ) belongs to {-1; 0}. In the first case, we know that the winding numbers of f around each element of Z in the interior of f is 1 which implies that ρ 2 ( exp ([f ] C Z )) = k. In the second case we similarly get that ρ 2 ( exp ([f ] C Z )) = -k.

The previous Theorem immediately implies the following corollary.

Corollary 4. If f is a Jordan curve in C Z so that 0 and 1 are in the interior of f then ρ 2 • e • f is k has a winding number that is either greater or equal to 2 or lower or equal to -2. f lies in C Z . It remains to show that f is a Jordan curve. Since g 1 and g 2 are both Jordan curves, we must have that f |[0;t] and f |[t;1] are both Jordan arcs. Thus if f is not a Jordan curve it must be from the fact that f |[0;t] intersects f |[t;1] , but, from the homotopy lifting property f |[0;t] is obtained from f |[0;t] by a homotopy that deforms it only in W 1 while f |[t;1] is obtained from f |[t;1] by a homotopy that deforms it only in W 2 and as W 1 and W 2 are disjoint, it cannot be the case that the two arcs intersect each other. Thus, f is a Jordan curve that is homotop to f in C 0,1 while [ρ 2 • exp • f ] C1 ∈ {-1; 0; 1} which leads to a contradiction.

Conclusion

We proved that M IX is a 2-MCFL, so that under the assumption that the class MCFLs capture the notion of mildly context sensitive languages, this proves that M IX is a mildly context sensitive language. Since mildly context sensitive languages, as Joshi described them, should exclude pathological languages such as M IX, this implies that the class of formal languages that captures mildly context sensitivity should be explored again. A natural candidate would be well-nested Multiple Context Free Languages (MCFL wn ) as defined in [START_REF] Kanazawa | The pumping lemma for well-nested multiple context-free languages[END_REF]. The interest of MCFL wn lies in the fact that they satisfy a strong form of pumping Lemma as proved in [START_REF] Kanazawa | The pumping lemma for well-nested multiple context-free languages[END_REF] while there is still no strong form of pumping Lemma for MCFL [START_REF] Kanazawa | Generating control languages with abstract categorial grammars[END_REF]. Thus the class of MCFL is quite challenging in terms of open problems. Furthermore, the grammar we propose to capture O 2 (and the one we would deduce for M IX) strongly relies on non-well-nested rules, and it is easy to see that removing non-well-nested rules weaken the generative capacity of the grammar (for example when removing this rule the word aabbā bābbaaa bbbb āāāb is no more in the language generated by the grammar). Thus we conjecture that neither M IX nor O 2 is a MCFL wn . If our conjecture is right, and if we stick to the idea that M IX should not be a mildly context sensitive language, then MCFL wn seem to be a possible replacement for the capturing mildly context sensitivity. But on the other hand, the result that M IX is an MCFL shows that MCFL can be used to model certain scrambling phenomena. It is even known that if, for every k, O k (as defined in [START_REF] Michael | Real-time solutions of the origin-crossing problem[END_REF]) is an MCFL then this class should contain all the permutation closures of recognizable languages [START_REF] Latteux | Cônes rationnels commutatifs[END_REF]. According to [START_REF] Ginsburg | Afl with the semilinear property[END_REF], this would give a lot of control on scrambling phenomena (e.g. specify islands of scrambling). But the problem of showing whether O 3 is an MCFL appear to be quite challenging. Indeed, the proof we give strongly relies on the Jordan curve Theorem, e.g. for the definition of the invariant that the curve representation of words satisfy in the case 5, for Lemma 16 and in Theorem 5. Thus before trying to obtain any result on this problem, it seems reasonable to try and find an alternate proof that O 2 is an MCFL that would avoid the detour through geometry.

On the side of the word problem for Z 2 , it is still open whether it can be solved by indexed grammars. We conjecture it is not the case. Indeed, MCFL wn can be seen as non-duplicating macro languages as introduced by [START_REF] Michael | Grammars with macro-like productions[END_REF] which are properly contained in indexed languages which are actually macro languages using the OI mode of derivation. It seems to us that semilinear rational cones (or semilinear Full Trio) that are included in indexed languages should be included in the class of MCFL wn . And as the rational cone generated by O 2 is semilinear, if our first conjecture and our intuition about semilinear rational cones included in the class of indexed languages are correct, then it would follow that neither O 2 nor M IX are indexed languages.

  and (a; b] for the set {(1 -t)a + tb | 0 ≤ t < 1}. With this convention [a; b] = [b; a], (a; b) = (b; a) and [a; b) = (b; a]. Sets of the form [a; b] and (a; b) are as usual respectively called closed intervals and open intervals. A closed interval [a; b] is said trivial when a = b and non-trivial otherwise.

  and O 2 are a 2-MCFLs Assuming for the moment Theorem 1, we are going to prove that M IX = {w ∈ {a; b; c} * ||w| a = |w| b = |w| c } and O 2 = {w ∈ {a; ā; b; b} * ||w| a = |w| ā ∧ |w| b = |w|b} are 2-MCFLs. Since the languages M IX and O 2 are rationally equivalent (i.e.

Figure 1 :

 1 Figure 1: C(w) when w = aaabaabaabbbbbaabbabbbbaaaabbbbbbbbaaa

w 1 =Figure 3 :

 13 Figure 3: Possible independant configurations for the last case of the proof

Figure 4 :

 4 Figure 4: Examples of case 5

Figure 5 :

 5 Figure 5: Curve representation of aabbā bābbaaa bbbb āāāb

Figure 7 :

 7 Figure 7: Parsing of aabbā bābbaaa bbbb āāāb

Figure 8 :

 8 Figure 8: Representative curves of the classes denoted by the fundamental groups generators

  Because E does not satisfy Q, we must have E ∩ C ∈C C = ∅ and by Lemma 11 E ∩ C ∈C C ⊆ {a; b}. Thus, given C in C , if C ∩ E = ∅, then we must have C = [c; a] with 0 ≤ c ≤ a or C = [b; c] with b ≤ c ≤ 1. We let D be the union of E with the intervals of C that E intersects; with the previous remark and the fact that C is a transitive system of closed interval, D is in C. By construction of D, if, for some C in C, D ∩ C = ∅, then C ⊆ D. But, as C is included in D and as C cannot be included in C , we have that for every C in C , C ∩ D = ∅ implies that C ⊆ D and C = D. This contradicts the fact that C satisfies P.

  1. on [aIw ; a kw ], ϕ n+1 is the linear function such that ϕ n+1 (a Iw ) = ϕ n (a Iw ) and ϕ n+1 (a kw ) = ϕn(a Iw )+ϕn(b Iw ) 2 2. on [a kw ; b kw ], ϕ n+1 is the function constantly equal to ϕn(a Iw )+ϕn(b Iw ) 2 , 3. on [b kw ; b Iw ], ϕ n+1 is the linear function such that ϕ n+1 (b Iw ) = ϕ n (b Iw ) and ϕ n+1 (b kw ) = ϕn(a Iw )+ϕn(b Iw ) 2

ϕn( a Figure 9 :

 a9 Figure 9: Given w ∈ L n , the graphs of ϕn and ϕ n+1 on Iw

  1 ) is on f |[0;u1] and h(v 2 ) is on f |[u2;1] f |[0;u1] , f |[u1;u2] and f |[u2;1]are respectively drawn in red, green and blue.

Figure 10 :

 10 Figure 10: Prototypical examples of the cases of Corollary 3

Theorem 5

 5 If f is a Jordan curve in C Z if there are k elements of Z in the interior of f then the winding number ofρ 2 • e • f is either k or -k. Proof. If w is a word on {α k , α -1 k |k ∈ Z} * representing [f ] C Z , then ρ 2 ( exp ([f ] C Z )) = k∈Z |w| α k -|w| α -1 k

  ) show that h |[t 1 ;t 2 ] ≈ Cp g |[t1;t2] which finally implies that g is a conservative deformation of h. It remains to check that g that if g(t 1 ) = g(t 2 ) and [g |[t1;t2]

Preprint submitted to ElsevierDecember 13, 2010

These transductions are due to Makoto Kanazawa who communicated them to me while exchanging on the problem of MIX. We describe these rational transductions using the bimorphic characterisation due to Nivat[START_REF] Nivat | Transductions des langages de Chomsky[END_REF].

In what follows we use the trigonometric or counter-clockwise orientation of the plane.

Acknowledgement:

I would like to thank Philippe de Groote, Makoto Kanazawa and Géraud Sénizergues for fruitful discussions, their support and their patience when trying to understand my confusing explanations about curves. I wish also to thank Gilles Zémor for pointing to me the possible use of algebraic topology to cope with the problem on Jordan curves.

transforming f |Cj into f j . As the family (C j ) j∈J is made of pairwise disjoint intervals, we may define H as the following homotopy:

We let h(t) = H(1)(t). We first check that h is a conservative deformation of f , i.e. for any t 1 and t 2 from [0; 1] such that t 1 ≤ t 2 , then there are t 1 and t 2 in [0; 1] such that t 1 ≤ t 2 and h |[t1;t2] ≈ Cp f |[t 1 ;t 2 ] . We let in case t 1 is in C j1 for some j 1 in J we let t 1 = inf{t | t ∈ C j1 } and otherwise t 1 = t 1 . Similarly, in case t 2 is in C j2 for some j 2 in J we let t 2 = sup{t | t ∈ C j2 } and otherwise t 2 = t 2 . Remark that in any cases, [t 1 ; t 2 ] ⊆ [t 1 ; t 2 ], that if for some j in J, we have

We write x ∼ y when h is constant on the interval [x; y]. The relation ∼ is an equivalence relation on [0; 1] and we write x for the equivalence class of x. From what we have just seen above, it is obvious that the classes of ∼ that are not singleton sets are precisely the intervals of the family (C j ) j∈J .

Lemma 14 implies the existence of a continuous and increasing function, ϕ, from [0; 1] to [0; 1] such that:

1. ϕ(0) = 0 and ϕ(1) = 1, 2. ϕ is constant on each C j for every j in J 3. if ϕ is constant on an open interval U then there is j in J such that U ⊆ C j .

Then the function ψ from [0; 1]/∼ to [0; 1] such that ψ( t) = ϕ(t) defines a homeomorphism between [0; 1]/∼ (equipped with the quotient topology) and [0; 1]. The definition of ψ implies that

If we let h be the continuous function from [0; 1]/∼ to X such that h ( t) = h(t), we then define g to be h • ψ -1 . The definition of h and identity (3) imply

We first show g is a conservative deformation of h. For this we are going to prove that for each t 1 and t 2 in [0; 1] such that t 1 ≤ t 2 , there is

. Indeed, let t 1 and t 2 be such that ϕ(t 1 ) = t 1 and ϕ(t 2 ) = t 2 (such t 1 and t 2 exist since ϕ is a surjection). Using (4) we have that g(t 1 ) = g(ϕ(t 1 )) = h(t 1 ) and g(t 2 ) = g(ϕ(t 2 )) = h(t 2 ), so let

1. the elements of N are pairwise disjoint, 2. for every C in

By uniform continuity of g, it is easy to see that there is ρ such that every [t

for 0 < k < n, then using Lemma 9 we get that

which contradicts the fact that Z g ∪ N g is empty. This then implies that [g |[u1;u2] ] Cp = 1. And since g is a conservative deformation of f , the conclusion follows.

A corollary of this Lemma is the following.

Corollary 3. If f is a closed curve in C p whose winding number is 1 (resp. -1) and f is not simple then there are

] has winding number 0 or 1 (resp. -1).

Proof. Let t 1 and t 2 be such that t 1 < t 2 , [t 1 ; t 2 ] [0; 1] and f (t 1 ) = f (t 2 ) (t 1 and t 2 exist since f is supposed not to be simple), then f |[t1;t2]] is a curve that has k as winding number. If k = 0 then the conclusion is obvious. If k > 0 then we can conclude using the previous Lemma. If k < 0 then thanks Theorem 4 and Corollary 4 are enough to prove Theorem 1.

Theorem 1 If f is a Jordan curve of C such that f (0) = A and f (t) = D for some t in (0; 1) and there are two points A and D in the interior of f such that D -A = D -A , then there is t 1 and t 2 such that t 1 < t 2 and one of the following property holds:

Proof. Without loss of generality, we may assume that A = 0 and D = 1. For any homotopic deformation of

While, if we suppose that f does not fulfill the conclusion of the Theorem then, from Theorem 4, we get that the curve of g = exp • f is so that g 1 = g |[0;t] and g 2 = g |[t;0] are Jordan curves of C 0 and that their respective winding numbers in C 0 are 1 and -1.

In case g lies in C 0,1 , i.e. there is no t such that g(t ) = 1, Lemma 6 implies that the respective winding numbers of g 1 and g 2 in C 1 are respectively in {0; 1} and {-1; 0} so that, in C 1 , g has a winding number in {-1; 0; 1}. But we have that

In case g -1 (1) = ∅, we are going to deform g with an homotopy into a curve g so that:

1. g -1 (1) = ∅ 2. with the homotopy-lifting property, this deformation corresponds to a deformation of f in C 0,1 which will allow us to obtain a contradiction similarly to the previous case.

There are four possibilities: only g 1 goes through 1, only g 2 goes through 1, g 1 (1) = g 2 (0) = 1, and g 1 and g 2 go both through 1 with g 1 (1) = 1 and g 2 (0) = 1. We are only going to treat this last case (the case g 1 (1) = g 2 (0) = 1 is easy and the other cases can be done in a similar way). This means that there is t

Since f is a Jordan curve, we must have that k 1 = k 2 . Let V be an open neighborhood of 1 that is evenly covered by exp, we let W 1 be the intersection of exp -1 (V ) with an open neighborhood of k 1 . Obviously V 1 = exp(W 1 ) is also evenly covered by exp, we can then perform an homotopy on the part of g 1 that lies in V 1 in order to obtain a Jordan curve g 1 that does not go through 1. Similarly, we can obtain W 2 that is the intersection of exp -1 (V ) with an open neighborhood of k 2 , note that W 1 and W 2 are disjoint and cannot contain either 0 or 1. We can then obtain a Jordan curve g 2 that does not go through 1 by deforming the part of g 2 that lies in V 2 = exp(W 2 ) with a homotopy. Let g be g 1 • g 2 , we call f the unique curve of C Z that can be obtained with unique path-lifting property of exp applied to g and so that f (0) = f (0). Using the homotopy-lifting property we have that f is homotop to f in C 0,1 , furthermore