Nicolas Stroppa
email: nstroppa@computing.dcu.ie

François Yvon
email: yvon@enst.fr

Formal Models of Analogical Proportions

Formal Models of Analogical Proportions

Natural Language Processing (NLP) applications rely, in an increasing number of operational contexts, on machine learning mechanisms which are able to extract, in an entirely automated manner, linguistic regularities from annotated corpora. Among these, analogical learning is characterized by the systematic exploitation, in a symbolic machine learning apparatus, of formal proportionality relationships that exist between training instances.

In this paper, we propose a general definition of these proportionality relationships, based on a generic algebraic framework. This definition is specialized to handle a number of representations that are commonly encountered in NLP applications, such as words over a finite alphabet, feature structures, labeled trees, etc. In each of these cases, we provide and discuss algorithms for answering the two main computational challenges posed by proportionality relationships: the validation of a proportion and the computation of the fourth term of a proportion. 1

Introduction

An analogical proportion1 is a relationship between four entities (x, y, z, t), denoted by x : y :: z : t and which reads "x is to y what z is to t". An example of such a proportion is: "planets are to the sun what electrons are to the atomic nucleus".

The ability to dynamically perceive and establish such analogical relationships is often recognized to lie at the core of human cognition [START_REF] Indurkhya | Metaphor and cognition: an interactionist approach[END_REF]Gentner et al., 2001;[START_REF] French R | The computational modeling of analogy-making[END_REF]. Tests involving verbal or geometric analogies constitute one basic ingredient of many IQ tests such as, for instance, the SAT college entrance test [START_REF] Hoffman R | Monster analogies[END_REF].

These kinds of proportions have been extensively studied in Artificial Intelligence, mostly in the context of Analogical Reasoning and Problem Solving (see e.g. [START_REF] Evans | A program for the solution of a class of geometric analogy intelligence test questions[END_REF]Hofstadter & the Fluid Analogies Research Group, 1995;[START_REF] Wilson | Solving proportional analogy problems using tensor product networks with random representations[END_REF][START_REF] Levine | A neural network theory of proportional analogymaking[END_REF][START_REF] Schmid | An algebraic framework for solving proportional and predictive analogies[END_REF] to name just a few). The main focus of these studies is the dynamic process of analogy-making which relates situations which, while being apparently very different, share a set of common high-level relationships. In the above mentioned example, both the solar system and the atom involve the rotation of one object around a centre, suggesting that the causes of these movements could be similar: the identification of the analogical proportion thus makes possible the transfer of knowledge from the solar system domain to the atom domain.

The notion of analogical proportion also has a long history in linguistics. It was revitalized in the early 20 th century by the work of de [START_REF] De | Cours de linguistique générale[END_REF], for whom proportions are the basis of analogical creations, a process involved in the construction of novel words. Proportions are also prevalent in modern theories of morphology, such as word-based morphology and related approaches [START_REF] Matthews | Morphology[END_REF][START_REF] Anderson | A-Morphous Morphology[END_REF][START_REF] Stump | Inflectional Morphology[END_REF][START_REF] Blevins | Word-based morphology[END_REF]. 2 In these models, the analysis of surface word forms is based primarily on their systematic relationships with other full forms. This is in sharp contrast with morphemic approaches of morphology, which decompose word forms into minimal units such as morphemes. An example proportion between word forms is:

"believe is to unbelievable what forgive is to unforgivable".

The (formal) proportion between these surface forms denotes here a deeper relationship between linguistic entities: the proportion also holds for the morphological features (part-of-speech, genre, number, etc.) that are associated with them. Moreover, given the morphological features of the first three forms, it is possible to infer the morphological features of the fourth one by solving the analogical equation3 "M(believe) is to M(unbelievable) what M(forgive) is to ?", where M (u) denotes the bundle of morphological properties associated with u.

Based on this observation, memory-based learning devices have been proposed to solve various Natural Language Processing (NLP) tasks such as automatic word pronunciation [START_REF] Yvon | Pronouncing unknown words using multi-dimensional analogies[END_REF], morphological analysis (Lepage, 1999a;[START_REF] Pirrelli | The hidden dimension: paradigmatic approaches to data-driven natural language processing[END_REF] and syntactic analysis [START_REF] Lepage | Open set experiments with direct analysis by analogy[END_REF]. These devices require the identification of formal analogical proportions between linguistic representations. 4 From a computational perspective, two key procedures need to be implemented: a validation procedure, which assesses the validity of a proportion; and a resolution procedure, which computes the fourth term of an analogical equation. These attempts have been limited by the types of representations they were able to handle: in most cases we know of, proportions were only defined on finite sequences over a finite alphabet, using a restricted or ad-hoc definition of the notion of proportion [START_REF] Yvon | Paradigmatic cascades: a linguistically sound model of pronunciation by analogy[END_REF][START_REF] Lepage | Solving analogies on words: an algorithm[END_REF].

The main contribution of this paper is thus to establish a general and consistent framework for the notion of analogical proportion, which is necessary to widen the scope of application of these learning devices and make them applicable for a wider range of linguistic representations and NLP tasks. We therefore present a general model for analogical proportion, which is applicable to several algebraic structures, including free monoids and sets of trees. We show that this framework is a "natural" generalization of extant definitions of proportions between simple objects, and explain how this framework can be instantiated to yield a suitable computational model for complex and/or structured representations such as words, trees, feature structures, and languages, which are all commonly used in NLP applications. This contribution has both a methodological and a computational aspect: in addition to a sound definition of proportions, we are also interested in the algorithmic complexity of the associated validation and resolution procedures.

The potential of analogy-based learners using these procedures has already been studied experimentally, for example in [START_REF] Stroppa | Définitions et caractérisations de modèles à base d'analogies pour l'apprentissage automatique des langues naturelles[END_REF][START_REF] Stroppa | An analogical learner for morphological analysis[END_REF][START_REF] Lepage | Purest ever example-based machine translation: Detailed presentation and assessment[END_REF][START_REF] Stroppa | Du quatrième de proportion comme principe inductif : une proposition et son application à l'apprentissage de la morphologie[END_REF][START_REF] Langlais | Translating unknown words by analogical learning[END_REF]. In this paper, we deliberately focus on the theoretical foundations of the learning process, i.e. proportions. Note that both [START_REF] Stroppa | Définitions et caractérisations de modèles à base d'analogies pour l'apprentissage automatique des langues naturelles[END_REF] and [START_REF] Stroppa | Définitions et caractérisations de modèles à base d'analogies pour l'apprentissage automatique des langues naturelles[END_REF] report experiments carried out on phonology and morphology learning tasks, in which one has to predict a pronunciation or a morphological analysis given an input word form. In the case of pronunciation, the output to predict is a sequence (of phonemes); in the case of morphological analysis, one may predict a (morphological) tree or a feature structure (of morphological features). These experiments demonstrate the ability of the approach to deal directly with various structured data while achieving state-of-the-art results; they are based on ALANIS5 (A Learning-by-Analogy Inferencer for Structured data), the tool we developed to implement the theoretical framework that we describe here. [START_REF] Lepage | Purest ever example-based machine translation: Detailed presentation and assessment[END_REF] introduce a machine translation system entirely based on this learning procedure: the input is a sequence of words in one language and the output a sequence of words in another language. [START_REF] Langlais | Translating unknown words by analogical learning[END_REF] use an analogical learner in the context of unknown words translation.

The remainder of this paper is organized as follows. To begin with, we introduce in Section 2 several examples of proportions that we want to model. In Section 3, we establish a general definition of analogical proportions, suitable for the following algebraic structures: semi-groups, free monoids, and lattices. This definition readily yields a suitable model for words, sets, and feature structures. The case of proportions between languages and labeled trees are addressed in Sections 4 and 5 respectively. We conclude and discuss avenues for further research in Section 6.

Examples of Analogical Proportions

In this Section, we present some examples of proportions between linguistic representations that we want to model. We start with the case of words, then consider the case of trees, sets, and feature structures, using examples borrowed or adapted from [START_REF] Matthews | Syntax. Cambridge Textbooks in Linguistics[END_REF][START_REF] Lepage | De l'analogie rendant compte de la commutation en linguistique[END_REF][START_REF] Yvon | Finite-state machines solving analogies on words[END_REF].

Analogical Proportions between Words

Word forms occurring in texts or lexicons are represented using strings, i.e. sequences over some finite alphabets. We want to model the following examples of proportions between word forms in English:

wolf : wolves :: leaf : leaves, reader : unreadable :: doer : undoable, unhappy : unhappiest :: dirty : dirtiest, in Latin: oratorem : orator :: honorem : honor, ([speaker, accusative] : [speaker] :: [honor, accusative] : [honor]), and in Arabic:

ArsAlA : mursilin :: AslAmA : muslimin ([They (two) sent] : [senders] :: [They (two) became Muslims] : [Muslims]).

Proportions between word forms are often a sign of deeper relationships between the entities represented by these forms. Proportions can also be misleading, as in for instance the coincidental proportion ear : early :: dear : dearly. 6 Conversely, many morphological relationships between lexical entries do not translate into a proportion between their orthographic or phonetic representations: slept is the past tense form of to sleep, just as gave is the past tense form of to give; yet we do not observe a proportion between these four word strings.

As is obvious from these examples, our main focus is on syntactic (formal) proportions, i.e. proportions in which a word form is viewed as a meaningless sequence of letters (or more generally, of symbols over a finite set). We therefore do not recognize semantic relationships such as "cow is to calf what mare is to foal" as a valid proportion over words. This does not mean that our model is unable to handle these proportions, as will be demonstrated shortly, but rather that these relationships hold at a different level of representation than mere word strings.

Analogical Proportions between Trees

Trees are commonly used in linguistic representations, to make explicit the internal structure of complex words or sentences. Trees also constitute a natural representation of first order predicates, used in the representation of the semantics of linguistic entities. An example of proportion between syntactic trees, adapted from [START_REF] Matthews | Morphology[END_REF] and which shows active/passive opposition, is displayed in Figure 1. [START_REF] Matthews | Morphology[END_REF]).

Such examples suggest that proportions may have the potential to handle some complex syntactic relationships between utterances, subject to the choice of an appropriate representation of these utterances (here, a representation that makes explicit the structural dependencies between words and phrases). Indeed, if we only consider the surface representations of these sentences (viewed as mere sequences of characters or words), the proportion ceases to hold. The ability to handle structural proportions such as the one in Figure 1 is thus an essential step to make analogical learning devices such as the one introduced in [START_REF] Pirrelli | The hidden dimension: paradigmatic approaches to data-driven natural language processing[END_REF] applicable for Parsing or Example-Based Machine Translation tasks.

Tree representations can also be used to represent first-order logic predicates. We can also model the analogy "cow is to calf what mare is to foal", assuming a first-order representation of the meaning of these words (see Figure 2).

Analogical Proportions between Sets

Classes are often used to represent discrete properties of a finite collection of linguistic entities. For example, a classical approach to the description of phonological systems identifies subclasses (subsets) of phonemes. Each class contains phonemes that share one or several properties: the class of consonants, of vowels, of stops, of consonant stops, etc. In this context, analogical proportions between sets of phonemes can be used to model systematic oppositions between these properties. For instance, the proportion displayed in Figure 3 relates stops (x), sibilants (t), voiced (y) and unvoiced (z) occlusive consonants.

x = { /b/, /p/, /t/, /d/, /k/, /g/ } : y = { /b/, /d/, /g/, /z/, /v/, /Z/ } :: z = { /p/, /t/, /k/, /s/, /f/, /S/ } : t = { /s/, /z/, /f/, /v/, /S/, /Z/ } Figure 3: Analogical proportion between sets of phonemes.

Analogical Proportions between Feature Structures

Systems of binary oppositions such as the one used in phonology can also be represented using feature structures, where each phoneme is associated with a vector of binary features. There is one feature for each subset of phonemes; a feature takes the value + whenever the phoneme belongs to the related set. Using this representation, the fact that the opposition between /t/ and /d/ on the one hand, and /s/ and /z/ on the other hand is analyzed in terms of voiced/unvoiced alternation can be modeled by the proportion between the corresponding feature sets (see Figure 4). Binary feature structures are also used in semantic representations: Figure 5 gives another view on the proportion "cow is to calf what mare is to foal".

Finally, feature structures are routinely used in NLP to represent syntactic structures. In the example of Figure 6, a proportion involving four such representations is displayed. Note that, in contrast to the two examples above (cf. Figures 4 and5), the structures involved in this proportion are complex: the value of a feature can be another

Summary

We have introduced above a number of examples of proportions between linguistic representations. Being able to identify these proportions is a requirement for the application of some analogical learners to NLP tasks [START_REF] Pirrelli | The hidden dimension: paradigmatic approaches to data-driven natural language processing[END_REF][START_REF] Stroppa | Définitions et caractérisations de modèles à base d'analogies pour l'apprentissage automatique des langues naturelles[END_REF].

From the examples we gave, it should be clear that we are interested in modeling formal proportions, i.e. proportions that can be identified solely using the forms of the representations and the nature of the algebraic structure underlying them. Moreover, we aim at providing a consistent framework that would be applicable to the various types of representations we introduced. Note that we are also interested in other types of structures, such as finite languages and directed acyclic graphs (which can represent syntactic dependency graphs).

Analogical Proportions on Algebraic Structures

In this section, we introduce a formal definition of the notion of analogical proportion.

We start with a general definition, which is then specialized and simplified for several algebraic structures, notably semi-groups, free monoids, groups and lattices. For each of these structures, we also discuss the computational aspects of the basic algorithms which respectively validate a proportion and compute the fourth term in a proportion.

A Generic Framework

How can we define the notion of analogical proportion in such a way that all the previous examples are covered? To start with, let us reconsider one of the examples given in Section 2, which we want to model. This example involves the four graphical forms: (unhappy, unhappiest, dirty, dirtiest). We can observe that the 1 st and the 2 nd forms share a prefix (unhapp-), so do the 3 rd and the 4 th forms (dirt-). Moreover, the 1 st and the 3 nd forms share a suffix (-y), so do the 2 nd and the 4 th forms (-iest). Each form can thus be analyzed with a prefix+suffix decomposition. This analysis suggests that the notion of analogical proportion between four terms is related to the ability to decompose each term into several smaller fragments (two fragments in the example above) that can be exchanged, i.e. that alternate. This intuition can be formalized as follows. Let U be a semigroup, i.e. a set equipped with an internal associative law ⊕. In order to express the notion of decomposition, we first introduce the auxiliary notion of factorization.

Definition 1 (Factorization).

A factorization of an element u of a semigroup (U, ⊕) is a sequence (u 1 , . . . , u n ), with ∀i ∈ 1, n , u i ∈ U , such that u 1 ⊕ . . . ⊕ u n = u.

Each term u i in a factorization of u is a factor of u. We note f u (i) = u i and

| f u | = n. If I = {i 1 . . . i k } ⊆ 1, n , we also note f u (I) = u i1 ⊕ . . . ⊕ u i k .
By taking into account the alternation constraint between the terms of a factorization, we can propose the following definition for analogical proportions. Definition 2 (Analogical proportion (semigroups)). Let (x, y, z, t) ∈ U 4 , we say that x : y :: z : t if and only if there exist some factorizations f x , f y , f z , f t , respectively of x, y, z and t, such that:

∀i ∈ 1, d , (f y (i), f z (i)) ∈ {(f x (i), f t (i)), (f t (i), f x (i))}.

By construction, we have

| f x | = | f y | = | f z | = | f z | = d.
The smallest integer d for which this property holds is termed the degree of the proportion.

Definition 2 expresses the alternation constraint by stipulating that all the factors f y (i) and f z (i) in y and z should be alternatively equal to factors in x or in t.

This definition is fairly general: it applies to any semigroup and a fortiori to any richer structure, such as those displayed in the inheritance graph of Figure 7. If the algebraic structure (U, ⊕) has additional properties (commutativity, existence of a neutral element, existence of a unique inverse for ⊕), then this definition can be simplified. We study several cases of such simplifications in the following paragraphs.

Before turning our attention to these simplications, we introduce a first result, which will prove useful in the following. Proof. It suffices to note that if

f u = (u 1 , . . . , u n ) is a factorization of u ∈ (U, ⊕), then F u = (M (u 1 ), . . . , M (u n )) is a factorization of M (u) ∈ (V, ), since M (u) = M (u 1 ⊕ . . . ⊕ u n ) = M (u 1 ) . . . M (u n ).

Abelian Semigroups and Abelian Groups

When the internal composition law in a semigroup U is commutative, the semigroup is said to be commutative or Abelian. Within an Abelian semigroup, the order of factors in a factorization is not relevant. When analyzing a proportion, it is thus possible to reorder the terms in a factorization of y so that the factors shared with x are put together on the "left part" of the factorization; and the factors shared with t are on the "right part". The same applies for z, hence the following result. Proposition 2.

If U is an Abelian semigroup, ∀(x, y, z, t) ∈ U 4 , we have x : y :: z : t if and only if

either (y, z) ∈ {(x, t), (t, x)} or ∃(x 1 , x 2 , t 1 , t 2 ) ∈ U 4 such that x = x 1 ⊕ x 2 , y = x 1 ⊕ t 2 , z = t 1 ⊕ x 2 , t = t 1 ⊕ t 2 .
Proof. One implication is true by virtue of definition 2.

To prove the converse, let us assume that there exists a quadruple of factorizations (f x , f y , f z , f t ) ∈ (U d ) 4 and two subsets I, J of 1, d such that I ∩ J = ∅, I ∪ J = 1, d , and:

f x (I) = f y (I), f z (I) = f t (I), f x (J) = f z (J), f y (J) = f t (J).
The composition law ⊕ being commutative, ∀α ∈ {x, y, z, t}, (f α (I), f α (J)) is a factorization of α, hence the result.

An Abelian group is an Abelian semigroup, i.e. a commutative monoid with identity element 1 U in which each element u has a unique inverse u such that u ⊕ u = 1 U . The definition of analogical proportions in Abelian groups can be further simplified. Proposition 3. If U is an Abelian group, ∀(x, y, z, t) ∈ U 4 , we have x : y :: z : t if and only if

x ⊕ ( y) = z ⊕ ( t).
Proof. Proposition 2 readily yields:

x ⊕ ( y) = x 2 ⊕ ( t 2 ) = z ⊕ ( t).
Conversely, if x ⊕ ( y) = z ⊕ ( t), taking:

x 1 = 1 U , x 2 = x, t 1 = z ⊕ ( x) and t 2 = y, yields: x = x 1 ⊕ x 2 , y = x 1 ⊕ t 2 , z = t 1 ⊕ x 2 and t = t 1 ⊕ t 2 .
This definition is consistent with traditional and intuitive visions of analogical proportions. For example, in (R , ×), it corresponds to the classical proportionality relation ( x y = z t ); in a vector space, it expresses the relation between the summits of a parallelogram ( x -y = z -t, cf. Figure 8). From a computational perspective, these simplifications make the computational problems of validating and solving a proportion a trivial issue, which basically amounts to performing two operations in U .

As we shall see in the coming sections, the same definition 2 that is used here to account for proportions between the summits of a parallelogram, or between integers in (N, +), will be used to establish proportions between sequences of letters or between trees, which is a positive sign of the consistency of our model.

Sets and Feature Structures

The abstract algebraic framework that has been presented in the previous section provides us with a definition of analogical proportion which readily applies to sets, multisets, and feature structures.

Sets

The union operation is an internal operation defined on the powerset (2 S , ∪) of a set S which makes it an Abelian monoid: it is associative, commutative and the empty set ∅ is the identity element. Proposition 2 directly applies. Proposition 4. Let S be a set, ∀(x, y, z, t) ∈ (2 S ) 4 , we have x : y :: z : t if and only if ∃(x 1 , x 2 , t 1 , t 2 ) ∈ (2 S ) 4 such that:

x = x 1 ∪ x 2 , y = x 1 ∪ t 2 , z = t 1 ∪ x 2 , t = t 1 ∪ t 2 .
It is routine to check that this definition accounts for the example given in Section 2.3 (cf. Figure 3).

Multisets

A multiset can be seen as a set whose elements have a multiplicity. Formally, a multiset is a pair (S, m) where S is a set (called the underlying set of elements) and m : S → N a function from S to the set N of (positive) natural numbers. For each element e in S, the multiplicity of e is m(e). 8 For convenience, a multiset (A, m) can also be noted a∈A m(a)a; for example, the multiset ({a, b}, m) such that m(a) = 2 and m(b) = 1 will be noted 2a + b.

A multiset is an Abelian monoid with respect to the sum operation ( ), defined as follows:

(A, m) (B, n) = (A ∪ B, f ), where f (e) = m(e) + n(e), ∀e ∈ A ∪ B.
Therefore, we can again apply proposition 2. We can easily verify that the following proportion holds:

3A + r + s + l : m + u + r + s + 2i + l + n :: 3A + s + l + m : 2m + u + s + l + 2i + n,
which is also a consequence of proposition 1, since: (i) the proportion between words ArsAlA : mursilin :: AslAmA : muslimin is verified (this will be formally proved in Section 3.4), (ii) the application that turns a word into a multiset of letters is a semigroup morphism.

Feature Structures

A feature structure is made up of a set of attribute-value pairs. A value can be either atomic or complex (most commonly a feature structure 9 ). Such representations are classical knowledge representation tools. Feature structures are also used in several formal models of syntax, such as LFG (Lexical Functional Grammar, [START_REF] Bresnan | Lexical-Functional Syntax[END_REF]) and HPSG (Head-Driven Phrase Structure Grammar, [START_REF] Pollard | Head-Driven Phrase Structure Grammar[END_REF])); [START_REF] Carpenter | The Logic of Typed Feature Structures[END_REF] gives an introduction to feature structures and their uses in NLP. A (matrix) representation of such a feature structure is displayed in Figure 9.

Feature structures can also be used to represent dependency relations, as produced by dependency parsers (Mel'čuk, 1988;[START_REF] Buchholz | CoNLL-X shared task on multilingual dependency parsing[END_REF], as displayed in Figure 10. Formally, the set of feature structures F S is a set equipped with two binary internal composition laws which are associative, idempotent, and commutative. The internal composition laws of the set F S are the unification operation, denoted and the generalization operation, denoted . The set F S is also equipped with a partial order relation, namely subsumption, denoted . We have a b if a is more general than b, i.e. if a b = a.

The set of feature structures being an Abelian semigroup for the unification operation, proposition 2 is also applicable. Proposition 5. ∀(x, y, z, t) ∈ F S 4 , we have x : y ::

z : t if and only if ∃(x 1 , x 2 , t 1 , t 2 ) ∈ F S 4 such that x = x 1 x 2 , y = x 1 t 2 , z = t 1 x 2 , t = t 1 t 2 .
It has to be noted that this definition applies to any kind of feature structure, the only requirement being the definition of the unification operation. Once again, it can be checked that this definition covers the introductory examples of Section 2.4.

Lattices

In this section, we present an additional simplification of previous definitions, which allows us to get rid of the existential quantifiers when the underlying algebraic structure is a lattice. The two cases of data structures studied in this section, namely sets and feature structures, are particular cases of lattices and will thus benefit from this simplified definition.

A lattice is a mathematical structure which can be seen either as a partially ordered set (poset) or as an algebra. A lattice can be defined as a poset in which all nonempty finite subsets have a least upper bound (also called supremum or join) and a greatest lower bound (also called infimum or meet). An algebra (L; ∧, ∨) is called a lattice if L is a nonempty set, ∧ and ∨ are binary operations in L, both idempotent, commutative, and associative, and satisfying the absorption law. These two views on lattices can easily be reconciled, and any lattice defined as an algebra can be turned into a lattice seen as a poset and vice-versa. This is stated in the following classical theorem [START_REF] Grätzer | Lattice Theory: First Concepts and Distributive Lattices[END_REF]:

Theorem 1. 1. Let the poset L = (L; ≤) be a lattice. Define a ∧ b = inf{a, b} and a ∨ b = sup{a, b}. Then the algebra L a = (L; ∧, ∨) is a lattice. 2. Let the algebra L = (L; ∧, ∨) be a lattice. Let a ≤ b if and only if a ∧ b = a (or equivalently a ∨ b = b). Then L p = (L; ≤) is a poset, and the poset L p is a lattice. 3. Let the poset L = (L; ≤) be a lattice; then (L p ) a = L. 4. Let the algebra L = (L; ∧, ∨) be a lattice; then (L a ) p = L.
The set of feature structures can be seen as a lattice with respect to the unification and generalization operations. The same applies to the powerset of a set with respect to the union and intersection operations. The following simplified definition of analogical proportion applies to these two types of representations. Proposition 6. If (L; ∧, ∨) is a lattice, ∀(x, y, z, t) ∈ L 4 , we have x : y :: z : t if and only if:

x = (x ∧ y) ∨ (x ∧ z), y = (x ∧ y) ∨ (t ∧ y), z = (t ∧ z) ∨ (x ∧ z), t = (t ∧ z) ∨ (t ∧ y).
Proof. ⇐ Trivial as the formulation of proposition 6 is a particular case of the one used in proposition 2.

⇒ Let (x, y, z, t) be in L 4 such that x : y :: z : t. By definition, there exists some

(x 1 , x 2 , t 1 , t 2 ) ∈ L 4 such that x = x 1 ∨ x 2 , y = x 1 ∨ t 2 , z = t 1 ∨ x 2 and t = t 1 ∨ t 2 .
We will first show that x = (x ∧ y) ∨ (x ∧ z). The inequalities

(x ∧ y) ∨ (x ∧ z) ≤ x ∧ (y ∨ z) ≤ x hold from the basic properties of meet and join. If a ≤ b and c ≤ d, then a ≤ b ≤ (b∨d) and c ≤ d ≤ (b ∨ d), yielding a ∨ c ≤ b ∨ d. Since x 1 ≤ x and x 1 ≤ y, we have x 1 ≤ (x ∧ y). Likewise, we have x 2 ≤ (x ∧ z). Consequently, x = x 1 ∨ x 2 ≤ (x ∧ y) ∨ (x ∧ z).
We therefore have

x = (x ∧ y) ∨ (x ∧ z),
and the other equalities hold by symmetry.

Based on this proposition, we can conclude that an algorithm for validating a proportion on sets or on feature structures will have the same complexity as the computation of the basic operations join and meet: in fact, validating an analogical proportion only involves 8 basic operations (4 meets and 4 joins). In the case of Boolean algebra, in which each element e has a complement ¬e such that e ∧ ¬e = 0, e ∨ ¬e = 1 and the two internal laws are mutually distributive, we have an additional result for the solving procedure.

Proposition 7.

If A is a Boolean algebra, we have x : y ::

z : t for (x, y, z, t) ∈ A 4 if and only if x ≤ (y ∨ z) and (y ∨ z) ∧ ¬x ≤ t ≤ (y ∨ z).
Proof. ⇒. We assume that the proportion x : y :: z : t holds. We thus have t = (t∧z)∨ (t∧y). From the basic properties of meet and join, we deduce t ≤ (y ∨z)∧t ≤ (y ∨z). Moreover, if we note y 1 = (x ∧ y), y 2 = (t ∧ y), z 1 = (t ∧ z), and z 2 = (x ∧ z), we have:

(y ∨ z) ∧ ¬x =((y 1 ∨ z 2 ) ∨ (z 1 ∨ y 2 )) ∧ ¬(y 1 ∨ z 2 ) =(z 1 ∨ y 2 ) ∧ ¬(y 1 ∨ z 2 ) =t ∧ ¬x ≤ t, so (y ∨ z) ∧ ¬x ≤ t ≤ (y ∨ z). Moreover, since x = (x ∧ y) ∨ (x ∧ z), we have x ≤ (y ∨ z).
⇐. We assume x ≤ (y ∨ z) and (y ∨ z) ∧ ¬x ≤ t ≤ (y ∨ z). Since x ≤ (y ∨ z), we have x ≤ x ∧ (y ∨ z), and x = (x ∧ y) ∨ (x ∧ z). We have (t ∧ z) ∨ (t ∧ y) ≤ t from the basic properties of meet and join. Moreover, since t ≤ (y ∨ z), we have

t ≤ t ∧ (y ∨ z), so t = (t ∧ z) ∨ (t ∧ y). Since (y ∨ z) ∧ ¬x ≤ t, we have ((y ∨ z) ∧ ¬x) ∨ x ≤ t ∨ x, and ((y ∨ z) ∨ x) ≤ t ∨ x. Consequently, we have both y ≤ t ∨ x and z ≤ t ∨ x, so y ≤ y ∧ (t ∨ x) and z ≤ z ∧ (t ∨ x). Finally, since (x ∧ y) ∨ (t ∧ y) ≤ y and z = (t ∧ z) ∨ (x ∧ z) ≤ z always hold, we can deduce y = (x ∧ y) ∨ (t ∧ y) and z = (t ∧ z) ∨ (x ∧ z).

Words

This section is devoted to the study of the free monoid structure, which is the classical model to represent finite sequences of symbols, that is, finite words. We use definition 2, which can be directly applied to the case of words. In particular, we examine the verification of the solving procedures and present a framework based on finite-state transducers.

A detailed presentations of proportions on words, including proofs, can be found in [START_REF] Yvon | Finite-state machines solving analogies on words[END_REF][START_REF] Yvon | Solving analogies on words[END_REF][START_REF] Stroppa | Définitions et caractérisations de modèles à base d'analogies pour l'apprentissage automatique des langues naturelles[END_REF], from where most definitions and constructions are borrowed. The discussion of the algorithmic aspects at the end of this section is entirely original.

Notations

Let Σ be a finite set of symbols, called an alphabet. Σ denotes the set of finite sequences of elements of Σ, called words over Σ. Provided with the concatenation operation, Σ is a free monoid whose identity element is the empty word . For x and y in Σ , the concatenation of x and y is denoted x.y or simply xy. We note | x | the length of x; we have | | = 0. For x ∈ Σ and i ≤ | x |, x(i) denotes the i th symbol in x.

Definition

For free monoids, we can rewrite definition 2; concatenation is the internal law used to define factorization in this case.

Definition 3 (Reformulation of Definition 2).

If Σ is a free monoid, ∀(x, y, z, t) ∈ Σ 4 , we have x : y :: z : t if and only if there exist some factorizations

(f x , f y , f z , f t ) ∈ ((Σ ) d ) 4 such that ∀i ∈ 1, d , (f y (i), f z (i)) ∈ {(f x (i), f t (i)), (f t (i), f x (i))}.
The smallest integer d for which this property holds is termed the degree of the proportion.

We can show [START_REF] Yvon | Finite-state machines solving analogies on words[END_REF] that this definition generalizes the (algorithmic) definition of proportions between words proposed by [START_REF] Lepage | Solving analogies on words: an algorithm[END_REF]; in both cases the following properties hold. First, an analogical equation may have one, zero, or multiple solutions. [START_REF] Lepage | Analogy and formal languages[END_REF] gives a number of conditions for an equation to have at least one solution; these conditions also apply here. In particular, if t is a solution of x : y :: z :?, then t contains all the symbols in y and z that are not in x, in the same order. As a corollary, all the solutions of an analogical equation (between words) have the same length.10

A Finite-State Solver

Proposition 3 yields an efficient procedure for solving analogical equations, based on finite-state transducers. We only sketch here the main steps of the procedure and we refer the reader to the above cited papers for a more detailed account. To start with, let us introduce the notions of complementary set and shuffle product.

Complementary Set If v is a subword of w, the complementary set of v with respect to w, denoted by w\v is the set of subwords of w obtained by removing from w, from left to right, the symbols in v. For instance, eea belongs to the complementary set of xmplr with respect to exemplar. When v is not a subword of w, w\v is empty. This notion can be generalized to any regular language.

The complementary set of v with respect to w is a regular set: it is the output language of the finite-state transducer T w (see Figure 11) for the input v.

0 1 2 k w(1) : ε ε : w(1) w(2) : ε ε : w(2) w(k) : ε ε : w(k)

Shuffle

The shuffle u • v of two words u and v is defined as follows [START_REF] Sakarovitch | Éléments de théorie des automates[END_REF]:

u • v = {u 1 v 1 u 2 v 2 . . . u n v n , with u i , v i ∈ Σ , u 1 . . . u n = u, v 1 . . . v n = v}.
The shuffle of two words u and v contains all the words w which can be composed using all the symbols in u and v, subject to the condition that if a precedes b in u (or in v), then it precedes b in w. Taking, for instance, u = abc and v = def , the words abcdef , abdef c, adbecf all belong to u • v; this is not the case of abef cd. This operation generalizes straightforwardly to languages.

The shuffle of two regular languages is regular [START_REF] Sakarovitch | Éléments de théorie des automates[END_REF]; the automaton

A, computing K • L, is derived from the automata A K = (Σ, Q K , q 0 K , F K , δ K ) and A L = (Σ, Q L , q 0 L , F L , δ L ) recognizing respectively K and L as the product automaton A = (Σ, Q K × Q L , (q 0 K , q 0 L ), F K × F L , δ)
, where δ is defined as: δ((q K , q L ), a) = (r K , r L ) if and only if either δ K (q K , a) = r K and q L = r L or δ L (q L , a) = r L and q K = r K .

The notions of complementary set and shuffle are related through the following property, which is a direct consequence of the definitions.

∀w, u, v ∈ Σ , w ∈ u • v ⇔ u ∈ w\v.

Solving Analogical Equations

The notions of shuffle and complementary sets yield another characterization of analogical proportion between words, based on the following proposition [START_REF] Yvon | Finite-state machines solving analogies on words[END_REF]: Proposition 8. ∀x, y, z, t ∈ Σ , x : y ::

z : t ⇔ x • t ∩ y • z = ∅.
An analogical proportion is thus established if the symbols in x and t are also found in y and z, and appear in the same relative order. A corollary follows: Proposition 9.

t is a solution of x : y ::

z :? ⇔ t ∈ (y • z)\x.
The set of solutions of an analogical equation x : y :: z :? is a regular set, which can be computed with a finite-state transducer. It can also be shown [START_REF] Yvon | Solving analogies on words[END_REF] that this analogical solver generalizes the approach based on edit distance proposed in [START_REF] Lepage | Solving analogies on words: an algorithm[END_REF].

Computational Issues

Given the finite-state constructions presented above, it is possible to assess the complexity of the validation and solving procedures. In the case of validation, we have to build the shuffles x • t and y • z, which yield two automata of size

| x + 1 | × | t + 1 | and | y + 1 | × | z + 1 | respectively.
We then have to intersect these automata, yielding an automaton of a most

| x + 1 | × | y + 1 | × | z + 1 | × | t + 1 |, which is then tested for emptiness. 11
The solving procedure is similar: we need to build the shuffle automaton of y and z, then to compute its complementary set with respect to x. Consequently, there is a nondeterministic automaton which represents the set of all possible solutions of x : y ::

z :? with O(| x | × | y | × | z |) states.
Enumerating all the words in this non-deterministic automaton is an exponential process, though this limit is rarely met in practice.

In the following, we present several ways to associate a numerical score to a proportion; these scores can be used to reduce the complexity of the solving procedure.

Scoring Analogical Proportions

Scoring analogical proportions serves two purposes. First, as analogical equations may have more than one solution, we need to define criteria allowing the comparison and ranking of competing solutions. Second, scoring proportions enables us to consider only a subset of optimal solutions when solving an analogical equation, which may reduce the complexity of the procedure. In the following, we present several score functions and discuss some of their properties. Additional measures of analogical proportions are presented in [START_REF] Yvon | Solving analogies on words[END_REF], based on the aggregation of measures of proportions between symbols of Σ.

(a) degree = 2 (b) degree = 3 1 1 1 1 2 2 2 s i n g s i n g i n g c a l l c a l l i n g 1 2 3 4 5 6 7 ← ------------------→ 1 1 1 1 2 2 2 3 3 s i n g s i n g i n g c a l l c a i n g l l 1 2 3 4 5 6 7 8 9 ← ------------------------→ size = 7 size = 9
Figure 12: The degree and size of two proportions on words (empty cells correspond to empty factors ( )).

Degree

The degree is a score function for proportions introduced in definition 2. The degree counts the number of alternating chunks in an analogical proportion: the smaller the degree, the simpler the proportion. The "trivial" proportions of the form a : a :: b : b or a : b :: a : b have a degree of 1. The degree is related to the number of factors found in the words involved in a proportion; a small degree corresponds the intuition that good proportions should preserve larger parts of the original words. The degree of an analogical proportion x : y :: z : t is denoted D(x : y :: z : t) and can be alternatively defined as followed, where F denotes the set of factorizations for which the proportion x : y :: z : t holds. Definition 4 (Degree). The degree of an analogical proportion x : y :: z : t is defined as follows:

D(x : y :: z : t) = min (fx,fy,fz,ft)∈F | f x |.
Size The degree counts the number of alternating factors. The size of a proportion counts the number of atomic symbol alignments, which take the form a : a :: b : b or a : b :: a : b (cf. Figure 12). Definition 5 (Size).

The size of an analogical proportion x : y :: z : t is defined as:

S(x : y ::

z : t) = min (fx,fy,fz,ft)∈F i∈ 1,| f x | max(| f x (i) |, | f t (i) |).
To illustrate the notions of degree and size, two examples are displayed in Figure 12. Whereas the analogical proportion sing : singing :: call : calling has a degree of 2 and a size of 7, sing : singing :: call : caingll has a degree of 3 and a size of 9, in agreement with the intuition that the former proportion is better than the latter.

-Order The -order of an analogical proportion is the maximum number of consecutive empty factors appearing in the factorizations involved in the proportion. For example, the proportion sing : singing :: call : calling has an -order of 1, whereas sing : singing :: call : caingll has an -order of 2: two consecutive empty factors appear in the related factorization of call (cf. Figure 12). Definition 6 ( -order). The -order of an analogical proportion x : y :: z : t with respect to α ∈ {x, y, z, t} is defined as:

O (x : y :: z : t, α) = min (fx,fy,fz,ft)∈F max 1≤i≤j≤| f x | {| j -i + 1 | : f α ( i, j ) = }
The -order for the whole proportion is defined as: O (x : y :: z : t) = max α∈{x,y,z,t} {O (x : y :: z : t, α)}

The -order is actually related to the notions of degree and size, yielding the following result. Proposition 10. If t is a solution of the equation x : y :: z :? such that D(x : y :: z : t) > O (x : y :: z : t, x) > 1, then there exists a solution t such that the following (in)equalities are satisfied:

O (x : y :: z : t, x) = O (x : y :: z : t, x) -1, D(x : y :: z : t) = D(x : y :: z : t) -1, S(x : y :: z : t) ≤ S(x : y :: z : t).
The proof of this proposition is given in Appendix A. In particular, this result implies that the search for a minimal degree solution of the equation x : y :: z :? can be pruned by searching only those words t which satisfy the inequality O (x : y :: z : t, x) ≤ 1.

Reducing the Complexity of the Solving Procedure Since the degree of an analogical proportion is a sign of its quality, it is possible to consider only solutions with a degree less than a given threshold.

To assess the complexity of this heuristic, let us first consider the case where the maximum degree is 2. In this case, factorizing three words amounts to considering a triple of positions which denotes the places where the factors separate. In Example (a) of Figure 12, the triple of positions of the factorizations is (4, 4, 4) in (x, y, z); in Example (b), the degree of the proportion is 3, so there are two triples of positions: (4, 4, 2) and (4, 7, 2). Once a triple of positions is chosen, we need to verify that the factor x i is equal to y i or z i . This verification requires at most

| y | + | z | = m operations. Since there are (| x |+1)×(| y |+1)×(| z |+1) = n triples of positions, the overall complexity is n × m.
If the maximal degree is d, then we have to consider d -1 triples of positions. The number of such triples is given by the multinomial coefficients.

For a degree d, the number of factorizations of

x is (x, d -1)! = | x |+d-1 d-1
(and likewise for y and z); the number of triples of positions is thus:

| x | + d -1 d -1 × | y | + d -1 d -1 × | z | + d -1 d -1 ,
which is bounded by a polynomial of degree d -1, hence the global complexity:

O((| x | × | y | × | z |) d-1 × m).
Here again, this theoretical complexity is rarely met in practice. A complementary approach consists in exploiting the result of the corollary 1. More precisely, if we are interested in solutions of low degree, then solutions involving consecutive epsilons may be safely skipped, which speeds up the search, though formal complexity is still polynomial in the product of the words lengths.

Multi-Level Proportions and Proportions between Languages

In this section, we present a generalization of the framework developed in the previous sections introduced in [START_REF] Yvon | Solving analogies on words[END_REF]. This generalization is needed to define proportions over languages. We then propose two possible definitions and show that they are in fact equivalent.

In the algebraic framework presented above, the notion of analogical proportion relies on: (i) the ability to decompose complex entities into smaller parts, (ii) the existence of alignments between these parts. Recall that four objects (x, y, z, t) form an analogical proportion if and only if there exist some factorizations (f x , f y , f z , f t ) of (x, y, z, t) such that:

∀i ∈ 1, n , (f y (i), f z (i)) ∈ {(f x (i), f t (i)), (f t (i), f x (i))}.
This latter condition states that it is possible to align the factors involved in the factorizations, forming quadruplets (f x (i), f y (i), f z (i), f t (i) that either match the pattern u : u :: v : v or u : v :: v : u. We have in fact already used this property when defining the size and the -order of a proportion between words over some finite alphabet. The left part of Figure 12 displays an alignment which supports the proportion sing : singing :: call : calling.

This property warrants the following alternative definition of proportions: Definition 7 (Recursive formulation of analogical proportions). For (x, y, z, t) ∈ U 4 , we have x : y :: z : t if and only if either (y, z) ∈ {(x, t), (t, x)},

or ∀α ∈ {x, y, z, t}, ∃(α 1 , α 2 ) ∈ (U, ⊕) 2 such that α = α 1 ⊕ α 2 and ∀i ∈ 1, 2 , x i : y i :: z i : t i .
It can be proved [START_REF] Stroppa | Définitions et caractérisations de modèles à base d'analogies pour l'apprentissage automatique des langues naturelles[END_REF]) that definition 7 is equivalent to definition 2.

This new definition makes explicit the fact that analogies on composite objects (i.e. objects that decompose in factors) are based on simple alternations between their factors, which will be termed base proportions in the remainder of this section.

In light of this reformulation of proportions, a natural extension is the consideration of a richer set of base proportions, giving rise to the concept of multi-level proportions. This extension is explored in the following section.

Multi-Level Proportions

Allowing arbitrary base proportions, definition 2 is generalized as follows. Definition 8 (Multi-level proportions). Let B(U ) denotes a set of base proportions, i.e. a subset of U 4 . For all (x, y, z, t) ∈ U 4 , we have x : y :: z : t if and only if either (x, y, z, t) ∈ B(U ) 4 or ∀α ∈ {x, y, z, t}, ∃(α 1 , α 2 ) ∈ (U, ⊕) 2 such that α = α 1 ⊕ α 2 and ∀i ∈ 1, 2 , x i : y i :: z i : t i , Denoting A(U ) the set of atomic proportions, definition 2 is obviously a particular case of definition 8 where A(U ) = B(U ). However, B(U ) may now contain more than the atomic proportions.

To illustrate this mechanism, let us consider the following example of analogical proportion between sequences of phonemes:

/aedvaIs/:/aedvaIz/::/bIli:f/:/bIli:v/ (advice : advise :: belief : believe) Definition 3 does not recognize this quadruplet as forming a valid proportion: alternating prefixes are easily identified, but no quadruplet of alternating suffix exists, as the alignment ( /s/:/z/::/f/:/v/ ) does not belong to the set of legitimate atomic proportions between individual phonemes. However, if we take into account the internal structural of the phoneme set, the proportion can be established. Let us consider each phoneme as a vector of distinctive binary features, as in Figure 4. In this context, the proportion ( /s/:/z/::/f/:/v/ ) is valid, and represent an instance of the opposition between voiced and unvoiced consonants.

To sum up, by considering an extended notion of analogical proportion between elements of the generator set Σ of the free monoid, we are in a position to generalize the notion of analogical proportion between elements of Σ . This strategy is fairly general, and allows us to stack together various levels of analogical proportions: it allows us, for instance, to define proportions between strings of sets, but also strings of strings, sets of features-structures, sets of strings of strings, etc. This generalization has obvious applications in the modeling of language, where the atoms of syntax (be they word forms or morphemes) are themselves made up of combinatorial arrangements of phonological atoms, a situation sometimes referred to in linguistic circles as the double articulation. Using two levels of proportions, the following four sentences, viewed as sequences of words, do constitute a valid multilevel proportion: dogs are resting by the fire : the cat sleeps on the coach :: cats are sleeping on the coach : the dog rests by the fire Figure 13: A two-level proportion.

In the following, we study the case where a definition of analogical proportions is available for a part P ⊆ U (typically for elements in the generative set of U , when U is a free semi-group). A proportion with respect to P between four entities (x, y, z, t) ∈ P 4 is denoted x : y P :: z : t; B(U ) is then simply defined as

B(U ) = {(x, y, z, t) ∈ P 4 | x : y P :: z : t}.
This formal extension is sufficient to define proportions for sets of strings, that is for languages, to which we now turn our attention.

Languages

Languages are commonly encountered in NLP applications: finite languages, for instance, provide a convenient model for ambiguities. They can be used to represent alternative analyses of a word, pronunciation variants, or a set of possible translations of a sentence.

An example of a proportion between finite languages, drawn from the word pronunciation task, is reproduced in Figure 14. As this example makes clear, our prime (potato) [p@"tA:t@] : [p@"tA:t@], [p@"teIt@] :: (tomato) [t@"mA:t@] : [t@"mA:t@], [t@"meIt@] interest in defining proportions between languages is to capture systematic ambiguities: in our example, the fact that a particular sequence of graphemes (ato) in a specific set of words is the subject of dialectal variations; in the context of automatic translation, the fact that two synonyms can be interchanged in almost every context.

A (finite) language over Σ is a (finite) subset of Σ . The set of languages is a semigroup with respect to the classical union operation. It is also a semigroup with respect to the concatenation operation, defined as:

L.K = {lk | l ∈ L, k ∈ K}.
Moreover, the concatenation is distributive with respect to the union and the neutral element for the union is a zero for concatenation, which makes the set of languages a semiring.

Languages can thus be studied from two different perspectives: (i) as sets of words and (ii) as elements of a semiring. Each of these perspectives entails a definition of analogical proportions between languages: the former suggests the use of the multilevel framework presented above; the latter points to an adaptation of definition 2 to algebraic structures equipped with two operators. In the following, we study these two definitions in more depth. They will eventually prove to be equivalent, which is a new piece of evidence in favour of the consistency of our framework.

Languages as Sets of Words

The set of languages over an alphabet Σ is 2 Σ . A language being a set of words, the multi-level framework is applicable: B(2 Σ ) is based on the definition of (usual or extended) analogical proportions between words, which correspond to the singletons in 2 Σ .

In order to distinguish between words and languages, analogical proportions between words will be denoted by x : y This is formally expressed by:12

B(2 Σ ) = {({x}, {y}, {z}, {t}) ∈ {{w}|w ∈ Σ } 4 | x : y Σ :: z : t} ∪ A(2 Σ ).
In this context, the definition of analogical proportion between words acts as a bootstrap for the case of languages. Our introductory example is correctly covered by this definition, and it is routine to check that: { p@"tA:t@} = { p@"tA:t@} ∪ { p@"tA:t@} { p@"tA:t@, p@"teIt@} = { p@"tA:t@} ∪ { p@"teIt@} { t@"mA:t@} = { t@"mA:t@} ∪ { t@"mA:t@} { t@"mA:t@, t@"meIt@} = { t@"mA:t@} ∪ { t@"meIt@} with p@"tA:t@ : p@"tA:t@ Σ :: t@"mA:t@ : t@"mA:t@ and p@"tA:t@ : p@"teIt@ Σ :: t@"mA:t@ : t@"meIt@. This notion of analogical proportion between languages will be called WLang and denoted x : y W :: z : t. The degree for a WLang proportion is defined as for the case of semigroups.

Languages as Elements of a Semiring

As already noted in Section 4.2, the set of languages is a semigroup with respect to both the classical union operation and the concatenation operation, which makes it a semiring. Building on this dual nature, it is possible to propose another generalization of analogical proportions, readily applicable to the case of languages. This generalization extends definition 2 as follows. Definition 9 (Analogical proportion (in a semiring)). If (U, ⊕, ⊗) is a semiring, ∀(x, y, z, t) ∈ U 4 , we have x : y :: z : t if and only if either (y, z) ∈ {(x, t), (t, x)}, or ∀α ∈ {x, y, z, t}, ∃(α 1 , α 2 ) ∈ U 2 and ∈ {⊕, ⊗} such that α = α 1 ⊕ α 2 and ∀i ∈ 1, 2 , x i : y i :: z i : t i . 13This definition is a simple extension of definition 2, in which two operators, rather than just one, can be used in factorizations.

A proportion on languages can thus be defined as a specific instance of definition 9, where the union and concatenation operations respectively instantiate ⊕ and ⊗. In this context, the notion of degree is well-defined and continues to refer to one plus the minimal number of recursions involved in a proportion.

This definition also correctly captures our working example, as:

{ p@"tA:t@} = { p@"t} . { A:} . { t@} { p@"tA:t@, p@"teIt@} = { p@"t} . { A:, eI} . { t@} { t@"mA:t@} = { t@"m} . { A:} . { t@} { t@"mA:t@, t@"meIt@} = { t@"m} . { A:, eI} . { t@}.

This notion of analogical proportion between languages will be called SLang and denoted x : y S :: z : t. In the case of SLang, the notion of degree is defined as the number of recursions involved in the proportion.

An Equivalence Result

In this section, we prove that the two definitions considered above are actually equivalent in the case of finite languages. Before developing the equivalence result, let us informally compare these definitions. Both involve two components: a definition of base proportions and a recursive mechanism of composition. In WLang, base proportions include atomic proportions and proportions between isolated words, and aggregation is made using the union operation; in contrast, in SLang, base proportions are the only atomic ones, but they can be recombined using both union and concatenation. WLang is based on an enriched notion of base proportion, while SLang draws upon a more liberal aggregation procedure. The proof additionally needs the following lemma.

Lemma 1. An atomic proportion between non-empty finite languages can be reinterpreted in terms of factorizations which only involve singletons.

Proof. Indeed, if A :

A W :: B : B with A = ∪ i k=1 {a k } and B = ∪ j k=1 {b k }, we can write: m = max(i, j), a k = a 1 for k ∈ i + 1, m and b k = b 1 for k ∈ j + 1, m ,
(x i ) i∈ 1,d , (y i ) i∈ 1,d , (z i ) i∈ 1,d , (t i ) i∈ 1,d so that ∀α ∈ {x, y, z, t}, α 1 ∪ • • • ∪ α d = α,
and ∀i ∈ 1, d , x i : y i W :: z i : t i (atomic proportion or proportion between singletons). If d = 1, then the quadruplet (x, y, z, t) is either an atomic proportion or a proportion between singletons. In the former case, the result is trivially verified. In the latter, x, y, z and t being singletons, we can note (x, y, z, t) = ({x }, {y }, {z }, {t }) with x : y Σ :: z : t . The definition of analogical proportion between words states that for α ∈ {x , y , z , t }, there exist some factors

(α i ) i∈ 1,d ∈ Σ so that α = α 1 . . . α m and ∀i, (y i , z i ) ∈ {(x i , t i ), (t i , x i )}.
If we set α i = {α i }, we then have: α = α 1 . . . α m (by concatenation of languages) with ∀i ∈ 1, m , (y i , z i ) ∈ {(x i , t i ), (t i , x i )} and α i = ∅. Since the definition of SLang allows for concatenations, we have x : y :: z : t, which establishes the implication for d = 1. The remaining of the inductive proof is trivial, as the composition mechanism is richer in the case of SLang than it is for WLang.

⇐. By induction on the degree of the proportion. Let (x, y, z, t) ∈ (2 Σ ) 4 with

x : y Let us now assume that the result holds for any proportion with degree k < d. By definition, ∃x 1 , x 2 , t 1 , t 2 ∈ (2 Σ ) 4 such that:

x = x 1 x 2 , y = x 1 t 2 , z = t 1 x 2 , t = t 1 t 2 ,
with ∈ {∪, .}, x 1 : y 1 S :: z 1 : t 1 and x 2 : y 2 S :: z 2 : t 2 . By definition of the degree of a proportion, we have D(x 1 : y 1 S :: z 1 : t 1 ) < d and D(x 2 : y 2 S :: z 2 : t 2 ) < d. Using the induction hypothesis, we thus also have x 1 : y 1 W :: z 1 : t 1 and x 2 : y 2 W :: z 2 : t 2 . If = ∪, the implication holds, since the union operation defines the aggregation mechanism of WLang, i.e. since:

x 1 : y 1 W :: z 1 : t 1 ∧ x 2 : y 2 W :: z 2 : t 2 ⇒ x : y W :: z : t.

If

= ., we can express the various factors involved as unions of proportions between singletons using Lemma 1,14 i.e. ∀α ∈ {x, y, z, t}, α 1 = ∪ i k=1 {α 1k }, α 2 = ∪ j k=1 {α 2k } with:

∀k ∈ 1, i , x 1k : y 1k Σ :: z 1k : t 1k and ∀l ∈ 1, j , x 2l : y 2l Σ ::

z 2l : t 2l .
It is consequently possible to write:

∀α ∈ {x, y, z, t}, α = α 1 α 2 = ∪ i,j k=1,l=1 {α 1k }{α 2l } = ∪ i,

Discussion

The equivalence result established above is a sign of the consistency of the framework.

For finite languages, the verification and solving procedures are decidable, though no efficient algorithm is known. In this case, a brute-force approach remains possible, by considering W Lang and the set of factorizations (with respect to the union operation) of a given language. 15 We do not have such a result in the case of infinite languages.

Tree Proportions

Labeled trees are commonly used in Natural Language Processing to represent linguistic entities: for instance, they can represent syntactic structures, or terms in the logical representation of a concept or of a sentence. Hence the need to provide a sound definition, and companion algorithms, for computing proportions on trees.

The definition of proportions between trees is quite similar to the one used for words and involves (i) associative binary operations between trees and (ii) the notion of alternating subtrees. The most obvious candidate operation, which is commonly encountered in tree-based grammar formalisms such as TSG [START_REF] Bod R | A computational model of language performance: Data oriented parsing[END_REF], is the left-most (label) substitution. However, this operation is not associative, which led us to ground our definition on the related notion of v-substitution (or substitution for short), which is the operation used to combine subtrees. This operation is introduced in section 5.1, followed in section 5.2 by a definition of tree proportions. We then turn to algorithmic issues, and successively study the case of exact and approximate computation of tree proportions. The main results of these studies are (i) exact algorithms for validating proportions between trees and for computing the solution of a proportion (section 5.3) and (ii) approximate algorithms for solving proportional equations on trees, which are based on more restrictive definition of proportions and exploit various linearizations of the input tree.

Notations and Definitions

The following notations and definitions are mainly borrowed and/or adapted from [START_REF] Comon | Tree automata techniques and applications[END_REF] and [START_REF] Shieber | Synchronous grammars as tree transducers[END_REF].

Definition 10 (Trees).

Let L be a finite set of labels, V a set of variables, and U = L ∪ V . The set of trees over U , denoted T (U ), is the smallest set such that:

• l ∈ T (U ) for all l ∈ U ; • f (t 1 , . . . , t n ) ∈ T (U ) for all f ∈ U and i ∈ 1, n , with t i ∈ T (U ).
Nodes in a tree are identified by their position, where a position is simply a sequence of positive integers, i.e. a word in N + . Position is the position of the root, 1 the position of its first (leftmost) child, 1.2 the position of the second child of its first child, and so forth. A set P os(t) of nodes positions is prefixial if

∀(u, i) ∈ (N + × N + ), u.i ∈ P os(t) ⇒ ∀j ∈ 1, i , u.j ∈ P os(t).
Prefixial sets are also termed tree domains. A tree such that Pos(t) = { } is called an empty tree.

A labeled tree t is thus a mapping from a tree domain P os(t) to U , where each node position is mapped to the label of the corresponding node. The label of node at position p in the tree t will be denoted t@p. This mapping is computed recursively as:

f (t 1 , . . . , t n )@ = f, f (t 1 , . . . , t n )@i.p = t i @p for i ∈ 1, n .
The set of variable positions in t is denoted by VPos(t) and V(t) is the set of variables in t. In the following, we will only consider trees in which these variables are located on leaves, i.e.:

∀u ∈ U, [u ∈ Pos(t) and ∃j, u.j ∈ Pos(t)] ⇒ t@u / ∈ V.
The yield of a tree t is the word in L defined as:

Y(l) = l, Y(f (t 1 , . . . , t n )) = Y(t 1 ). . . . .Y(t n ).
Example Let us consider the set of labels L = {a, b} and the set of variables V = {x}. The tree t 1 ∈ T (U ), defined as:

t 1 @ = t 1 @1 = t 1 @2.2 = a, t 1 @2 = t 1 @2.1 = b and t 1 @2.3 = x,
and the tree t 2 ∈ T (U ), defined as t 2 @ = t 2 @1.1 = t@1.2 = a, t@1 = t@2 = b, are displayed in Figure 15, where positions appear between parentheses. We have VPos(t 1 ) = {x}, VPos(t 2 ) = ∅, Y(t 1 ) = abax, and Y(t 2 ) = aab.

t 1 t 2 a( ) a(1) b (2) b(2.1) a(2.2) x(2.3) a( ) b(1) a(1.1) a(1.2) b (2)
Figure 15: Two examples of trees.

We are now in a position to introduce the notion of substitution.

Definition 11 (Substitution).

A substitution is a pair (v ← t ), where v ∈ V is a variable and t ∈ T (U ) is a tree. The application of the substitution (v ← t ) to a tree t is denoted t v t and is computed inductively as:

   v v t = t if v ∈ V, l v t = l if l ∈ L, f (t 1 , . . . , t n ) v t = f (t 1 v t , . . . , t n v t ).
In other words, the application of a substitution consists in replacing each leaf of t labeled v by the tree t . Example Continuing with the example trees of Figure 15, the application of substitution (x ← t 2 ) to t 1 yields t 1 x t 2 = t 3 (see Figure 16). A factorization of a tree t is a sequence of substitutions whose final result is t. Put in formal terms: Definition 12 (Factorization). A factorization of a tree t ∈ T (U ) is a pair [s, v ], where s is a sequence of trees (t 1 , . . . , t n ) and where v is a sequence of variables (v 1 , . . . , v n-1 ) such that:

• t 1 v1 . . . vn-1 t n = t; • ∀i ∈ 1, n , | {p ∈ P os(t i )| t i @p = v i } | = 1, where t i = t 1 v1 . . . vi-1 t i .
The second condition expresses an essential restriction in our model: each substitution in the factorization must operate exactly on one node. In the following, we will consider two different notations for factorizations.

Two factorizations that only differ in the naming of variables can be considered equivalent, which is formalized as follows. Let m : V 1 → V 2 be a bijective renaming of variables; by extension, m(t) denotes the tree t in which each variable v of V 1 has been replaced by the corresponding variable m(v) in V 2 . For a factorization [s, v] with s = (t 1 , . . . , t n ) and v = (v 1 , . . . , v n-1 ), we will also note

m([s, v]) = [(m(t 1 ), . . . , m(t n )), (m(v 1 ), m(v 2 ), . . . , m(v n-1 ))]. Since the renaming of variables is bijective, if [s, v ] is a factorization of t, then m([s, v ]) is also a factorization of t. Moreover, if we write [s, v ] ∼ [s , v ] if and only if there exists a bijective renaming of variables m from {v i } i∈ 1,n-1 to {v i } i∈ 1,n-1 such that m([s, v ]) = [s , v ],
then ∼ defines an equivalence relation.

In the following, we consider two different projection maps to refer to an equivalence class of factorizations using a particular representative of this class. In the first one, termed the "N notation", variables are denoted by their positions in the factorization, i.e. for a factorization [s, v]

with s = (t 1 , . . . , t n ) and v = (v 1 , . . . , v n-1 ), we have ∀i ∈ 1, n -1 , N (v i ) = i, i.e.: N ([s, v]) = [(N (t 1 ), . . . , N (t n )), (1, 2, . . . , n -1)].
In the second one, termed the "P notation", variables are denoted by the (unique) position in the tree where the substitution takes place, i.e.:

P ([s, v]) = [(P (t 1 ), . . . , P (t n )), (p 1 , p 2 , . . . , p n-1 )], with ∀i ∈ 1, n -1 , (t 1 v1 . . . vi-1 t i )@p i = v i .
We will say that a factorization [s, v ] is an N -factorization (resp. a P -factorization) if

N ([s, v ]) = [s, v ] (resp. P ([s, v ]) = [s, v ]).
By construction, there is only one Nfactorization and one P -factorization per equivalence class. In the following, we will only consider P -factorizations whose first tree to rewrite is the empty tree .

Analogical Proportions between Trees

Provided with the basic notions of substitution and factorization, we first introduce, and then discuss, a general definition of proportions between labeled trees. Definition 13 (Analogical proportion between trees). For (x, y, z, t) ∈ T (U ) 4 , we have x : y :: z : t if and only if there exist four factorizations

[s x , v], [s y , v], [s z , v], [s t , v] of x,
y, z, and t respectively, such that:

s x = (x 1 , . . . , x n ), s y = (y 1 , . . . , y n ), s z = (z 1 , . . . , z n ), s t = (t 1 , . . . , t n ), with ∀i ∈ 1, n , (y i , z i ) ∈ {(x i , t i ), (t i , x i )}.
As an additional restriction, we impose that the variables involved in the proportion appear in the same factors, i.e.

∀i ∈ 1, n , V(x i ) = V(y i ) = V(z i ) = V(t i ).
This definition is a direct adaptation of definition 2, in which subtrees are combined via substitutions. However, instead of using only one operator, we consider here a set of operators (one for each variable) and require that the variables involved in the four factorizations be identical. The first merit of this definition is thus its consistency with our general understanding of proportions.

It can moreover be shown that, given this definition, the "syntactic" proportion illustrated in section 2.2 holds (cf. Figure 1), as well as the more morphologicallyoriented example in Figure 17 (a). Figure 17 (b) uncovers the factorizations underlying this proportion. See also Figure 18 for a detailed view of the example in Figure 1.

V V |.V de V N colony V |N. ize N |V. ation v 1 N V V |.V de V v 1 V |N. ize N |V. ation v 1 N V V |.V de V v 1 V |N. ize N |V. ation (b) : :: : v 1 → N military v 1 → N military v 1 → N colony v 1 → N colony

Computing Proportions between Trees

This section is devoted to a study of the computational implications of this definition. We first present an exact algorithm for deciding whether four trees form a proportion and explain how to turn it into a solver. This algorithm however has an (at least) exponential worst case complexity. We thus consider approximate algorithms for verifying and solving proportional equations, which essentially put to use various tree linearization procedures and the available verifier and solver for proportions between sequences. These approximations are only valid for a more restrictive notion of proportions between trees. :: :

v 1 → the police v 1 → the police v 1 → the mouse v 1 → the mouse v 2 → impounded v 2 → impounded v 2 → eaten v 2 → eaten v 3 → his car v 3 → his car v 3 → the cat v 3 → the cat
Figure 18: Active/passive proportion (see Figure 1): explicit factorizations.

Validating Proportions between Trees

The algorithm we propose for validating proportions between trees is a constructive algorithm, which tries to build factorizations supporting the proportion. This algorithm is a two-step process:

1. For each tree α in {x, y, z, t}, create a finite-state automaton A α representing all the P -factorizations of α (cf. Algorithm 1).

2. Search for compatible factorizations within these automata, where compatibility is defined as in definition 13. This step puts to use some of the algorithms introduced in Section 3.4.3 to compute and validate proportions between words.

These steps are detailed in the following paragraphs.

Construction of the Automaton

Algorithm 1 is essentially a recursive exploration of all the possible decompositions of tree α in subtrees. Each state defines a set of positions where the variables are located, and where substitution will take place. Each transition corresponds to a substitution, which replaces a variable with a tree. If t is a leaf node, there are only two states, an initial state i associated to the variable position , and a final state f associated with the empty set ∅ -which means there is no variable to substitute. A (loop) transition on i substitutes with itself; a transition between i and f rewrites into l, the label of the unique node of t (Lines 1-4). If the tree t is not empty, we initialize the set of states with the initial state (associated to the variable position ), and the set of transitions with the loop over this initial state (Lines 5-6). We then build the automata A j for all the children t j of the root of t (Lines 7-8); indeed, a substitution can occur in any of these children, leaving the rest untouched, and we thus have to consider all the possible combinations of states (Lines 9-11). Transitions Algorithm 1: ConstructAutomaton(t,p)

Input : A tree t = l(t 1 , . . . , t n ) Output: An automata A = Q, E, i, f i ← { } 1 f ← ∅ 2 if n = 0 then 3 return {i, f }, {(i, i, → ), (i, f, → l)}, i, f 4 Q ← {i} 5 E ← {(i, i, → )} 6 for j ← 1 to n do 7 A j = Q j , E j , i j , f j ← ConstructAutomaton(t j ) 8 for (q 1 , . . . , q n ) ∈ Q 1 × • • • × Q n do 9 q ← 1.q 1 ∪ . . . • • • ∪ n.q n 10 Q ← Q ∪ {q} 11 for j ← 1 to n do 12 for (q j , q j , p → u) ∈ E j do 13 q ← 1.q 1 ∪ • • • ∪ (j -1).q j-1 ∪ j.q j ∪ (j + 1).q j+1 ∪ • • • ∪ n.q n 14 E ← E ∪ (q, q , j.p → add_pref(j, u)) 15 E ← E ∪ (i, q, → γ -1 (q)) 16 return Q, E, i, f
17 are built upon the set of substitutions (Lines 13-15) that occur in each child (loop in Line 12); add_pref(j, u) denotes the tree u in which the prefix j is added to all the variables (so as to turn a subtree of t j into a proper subtree of t). Finally, a substitution can directly rewrite , hence Line 16. 16 An example of a tree t and the associated A t is displayed in Figure 19. The proof of the following proposition can be found in Appendix B. Proposition 12.

The successful paths in A t are the P -factorizations of t.

Uncovering Consistent Factorizations

In order to validate a proportion, we now have to find factorizations that meet the requirements imposed by definition 13, i.e. factorizations involving alternating substitutions. In order to do this, our algorithm proceeds in two steps:17 • The first step extracts quadruples of P -factorizations s x , s y , s z , s t , with ∀α ∈ {x, y, z, t}, s α = [(α 1 , . . . , α n ), (p α1 , . . . , p αn-1 )], such that:

(a) A B C D (b) { } {1, 2} {2} {1, 2.1} {2.1} {1} ∅ → A /\ 1 2 1 →B 2 → C | 2.1 2 → C | 2.1 1 →B 2.1 →D 2.1 →D 1 →B
∀i ∈ 1, n , d(x i ) : d(y i ) :: d(z i ) : d(t i ),
where d denotes the operation which replaces all variables by a dummy symbol DUM. This extraction is achieved using the validation algorithm for strings introduced in Section 3.4.3. 18 Indeed, if this condition is verified, the paths c x , c y , c z , c t defined for α ∈ {x, y, z, t} as c α = (DUM → α 1 , . . . , DUM → α n ) form a valid proportion between strings (of "generalized" substitutions), and conversely.

• The second step consists in checking that it is possible to find a consistent assignment of the variables, consistent meaning here that the substitutions involved in the factorizations actually rewrite the same variables at the same time. Given the P -factorizations s x , s y , s z , s t , and noting for α ∈ {x, y, z, t}, N

(s α ) = [(α 1 , . . . , α n ), (1, . . . , n -1)], this is simply achieved by checking out that ∀i ∈ 1, n , (y i , z i ) ∈ {(x i , t i ), (t i , x i )}, and V(x i ) = V(y i ) = V(z i ) = V(t i ).
The correctness and completeness of the algorithm are proved as follows.

Proof. Correctness. By construction, the validation algorithm provides us with four factorizations f x , f y , f z , and f t respectively of x, y, z, and t such that

∀α ∈ {x, y, z, t}, N (f α ) = [(α 1 , . . . , α n ), (1, . . . , n -1)],
18 In particular, this step requires to build the shuffle products A x • A t and A y • A z and the intersection A x • A t ∩ A y • A z , where A α denotes the automaton Aα in which the variables have been "generalized" using a dummy symbol.

with ∀i ∈ 1, n , (y i , z i ) ∈ {(x i , t i ), (t i , x i )}, and V(x i ) = V(y i ) = V(z i ) = V(t i ).
We thus have x : y :: z : t. Completeness. By definition of proportion between trees, there exist four factorizations

[s x , v], [s y , v], [s z , v], [s t , v] of x,
y, z, and t respectively, such that ∀α ∈ {x, y, z, t}, s α = (α 1 , . . . , α n ),

with ∀i ∈ 1, n , (y i , z i ) ∈ {(x i , t i ), (t i , x i )} and V(x i ) = V(y i ) = V(z i ) = V(t i ).
By construction, for α ∈ {x, y, z, t}, the automaton A α contains the P -factorization

P ([s α , v]), which we note P ([s α , v]) = [(α 1 , . . . , α n ), (p α 1 , . . . , p α n-1 )]. We have: ∀i ∈ 1, n , (y i , z i ) ∈ {(x i , t i ), (t i , x i )}, so ∀i ∈ 1, n , (P (y i ), P (z i )) ∈ {(P (x i ), P (t i )), (P (t i ), P (x i ))}, and ∀i ∈ 1, n , (d(P (y i )), d(P (z i ))) ∈ {(d(P (x i )), d(P (t i ))), (d(P (t i )), d(P (x i )))}.
The validation algorithm will thus find the paths associated to P ([s α , v]) for α ∈ {x, y, z, t} and the first step of the algorithm will succeed. The last thing to check is:

∀i ∈ 1, n ,(N (y i ), N (z i )) ∈ {(N (x i ), N (t i )), (N (t i ), N (x i ))} and V(N (x i )) = V(N (y i )) = V(N (z i )) = V(N (t i )), which, again, is a direct consequence of ∀i ∈ 1, n , (y i , z i ) ∈ {(x i , t i ), (t i , x i )} and V(x i ) = V(y i ) = V(z i ) = V(t i ).
Complexity There is one state in A α for each antichain 19 of Pos(α). In the general case, the number of states is thus (at least) exponential with respect to the number of internal nodes; for a tree α = l(α 1 , . . . , α n ), the number of nodes π(α) is computed using the following recurrence, which can be established directly from Algorithm 1:

π(l) = 2 π(l(α 1 , . . . , α n )) =
1≤i≤n (1 + π(α i )). In the case of a tree made of one root directly dominating n -1 leaves, this number is π(α) = 3 n-1 . In the case of a balanced tree α of width k (the width is the constant branching factor of the internal nodes in α), we have π(α) ≤ k C×n , where C is a constant which depends only on k.

The complexity of the extraction and verification step in the worst case is thus at least exponential in the number of nodes of the trees. It is up to future work to establish whether this decision problem is N P -complete.

Solving Analogical Equations between Trees

Based on the algorithm presented above, it is possible to derive a solver for analogical equations between trees. Given three trees x, y, z, this solver constructs the automata A x , A y , A z , then build the shuffle product A y • A z , and use the complementary operation with respect to A x to obtain A y • A z \A x , where A α denotes the automaton A α in which the variables have been "generalized" using a dummy symbol. This gives a set of candidate sequences of substitutions. As is the case for verification, for each candidate we need to perform a check on variables to finally get the set of correct solutions for the equation x : y :: z :?. The complexity of this solver is established in the same manner as for the verification procedure.

Approximative Verification and Solving Algorithms

In this section, we present approximate algorithms aimed at validating analogical proportions and solving analogical equations, which rely on tree linearization procedures. These approximations are based on a more restrictive notion of proportions between trees, which is detailed below.

A tree linearization is an injective application from a set of trees to some free monoid; it establishes a unique correspondence between a tree and a string. We consider here two different tree linearization procedures. The first is based on parenthesized expressions; the second one is based on a prefix traversal of the tree, along which each node label and arity are collected. These linearizations are more formally defined as follows. Definition 14 (Parenthesized expressions). Let U be a set of labels and "(", ")" two symbols not in U . Ū denotes U ∪ {(, )}. The parenthesized expression of a tree t is the word p(t) ∈ Ū inductively defined as:20 p(f (t 1 , . . . , t n )) = (.f.p(t 1 ). . . . .p(t n ).).

Example By considering the tree t 3 of Figure 16, we have:

p(t 3 ) = (a(a)(b(b)(a)(a(b(a)(a))b))).

Definition 15 (Arity-based linearization).

The arity-based linearization of a tree t is the word ab(t) ∈ (L×N) inductively defined as:

ab(f (t 1 , . . . , t n )) = (f, n).ab(t 1 ). . . . .ab(t n ).

Example By again considering t 3 , we have: ab(t 3 ) = (a, 2)(a, 0)(b, 3)(b, 0)(a, 0)(a, 2)(b, 2)(a, 0)(a, 0)(b, 0).

In the following, we consider proportions in which factorizations involve variables appearing in the same relative lexicographic order in the four trees, i.e. for a proportion x : y :: z : t supported by the factorizations [(α 1 , . . . , α n ), (v 1 , . . . , v n-1 )] for α ∈ {x, y, z, t}, we add the following constraints:

∀α, α ∈ {x, y, z, t}, ∀i ∈ 1, n , ∀v j , v k ∈ {v 1 , . . . , v n }, if (α 1 v1 . . . vi-1 α i )@n j = v j , (α 1 v1 . . . vi-1 α i )@n k = v k , and (α 1 v1 . . . vi-1 α i )@n j = v j , (α 1 v1 . . . vi-1 α i )@n k = v k , then n j < n k ⇔n j < n k .
A proportion (between trees) satisfying these conditions will be noted x : y C :: z : t (C standing here for "constrained"). The rationale behind this additional constraint is that, in the case where it is verified, we can relate proportions between trees and proportions between their linearizations. In particular, if a proportion between trees holds, then this implies that there is also a proportion between their linearizations (seen as words). By doing so, we lose some of the expressiveness of proportions between trees (for example, a passive/active opposition cannot be captured); however, it makes the application of efficient algorithms possible, as demonstrated by the following result.

Proposition 13. For (x, y, z, t) ∈ (T (U )) 4 , we have:

x : y Proof. First, let us remark that for a tree t, and a variable v appearing exactly once in t, if p(t) = u 1 vu 2 , then for any tree t , p(t v t ) = u 1 p(t )u 2 .

The proof is established by induction on the degree n of the proportion. We will also prove that for any proportion x : y C :: z : t of degree n, if {v 1 , . . . , v k } is the set of variables appearing in x,y,z, and t, in lexicographic order, we have:

∀α ∈ {x, y, z, t}, ∃(u αi ) i∈ 1,k+1 ∈ Ū , so that p(α) = u α1 v 1 u α2 . . . v k u α k+1 , with ∀i ∈ 1, k + 1 ,
s α = (α 1 , . . . , α n ) for α ∈ {x, y, z, t}, with ∀i ∈ 1, n , (y i , z i ) ∈ {(x i , t i ), (t i , x i )} and V(x i ) = V(y i ) = V(z i ) = V(t i )
, and the additional specific constraint introduced above for C ::. If n = 1, the proportions are atomic, and since the variables appear in the four trees in the same lexicographic order, it is also the case for the variables in their linearizations. The implication is thus verified for n = 1.

We now assume that it also holds for any proportion of degree k < n. For α in {x, y, z, t}, we set α = α 1 v1 . . . vn-2 α n-1 and v = v n-1 , so we can write α = α v α n . The proportion x : y :: z : t clearly holds and its degree is at most n -1. The induction hypothesis thus yields: ∀α ∈ {x, y, z, t}, ∃(u αi ) i∈ 1,k+1 ∈ Ū , so that p(α ) = u α1 . . . v . . . u α k+1 , with ∀i ∈ 1, k + 1 , u xi : u yi :: u zi : u ti .

We then have p(α) = u α1 . . . p(α n ) . . . u α k+1 . Moreover, since the variables in x n , y n , z n , and t n appear exactly once and in the same relative order, we have p(x) : p(y) :: p(z) : p(t), as well as the property added to the induction hypothesis.

Proposition 14.

For (x, y, z, t) ∈ (T (U )) 4 , we have:

x : y Proof. The demonstration is directly obtained by replacing p(w) by ab(w) in the proof of proposition 13.

More generally, the proposition is true whenever the linearization respects the lexicographic order of the nodes.

These results warrant the use of an approximate verifier or solver based on tree linearization procedures. Moreover, it is possible to stack several verifiers or solvers based on various linearizations in order to get closer to the exact solutions. We can also use these procedures as a generating device, which proposes analogical proportions which will then be validated or filtered by the exact algorithm presented in the previous section.

Summary

In this section, we have defined two alternative notions of proportions between labeled trees. The first one is more general and covers a wider range of linguistic phenomena. Notably, it relates structures in which constituents are moved from one position in the tree to another, as is the case in active/passive transformations. Based on this first definition, we have presented an exponential algorithm for validating proportions, and for solving equations.

The second definition is more restrictive, as it requires that constituents should occur in the same positions in the trees. However, it lends itself to faster, albeit approximate, algorithms, which can be used in a two-step validations procedure.

Both definitions can be further generalized in a manner similar to the generalization discussed in Section 4: by replacing the condition that the labels occurring on leaf nodes should match exactly by the less stringent requirement that they define a proportion on sequences.

Conclusion and Perspectives

Conclusion

In this paper, we have introduced a formal algebraic framework for the notion of analogical proportions. This framework applies to a large range of algebraic structures: semigroups, free monoids, lattices, languages, and sets of trees. This framework is based on the decomposition of objects into smaller parts that alternate. Depending on the actual structure, the generic definition we propose may be simplified, and the verification and solving procedures may be more or less expensive. We discussed the algorithmic complexity of these procedures in several cases. Efficient algorithms are available for strings, feature-structures, and sets. In the case of trees, we can build approximate algorithms upon various linearizations. This yields a computational model suitable for most structured representations commonly used in NLP applications. Moreover, the examples of proportions we planned to model are covered by our definitions.

This framework has been implemented within the software ALANIS21 (A Learningby-ANalogy Inferencer for Structured data): learning devices that are based on analogical proportions can benefit from this implementation and are now applicable to a wide range of linguistics representations and NLP tasks. The results of several experiments using this software are actually reported by [START_REF] Stroppa | An analogical learner for morphological analysis[END_REF]; [START_REF] Stroppa | Définitions et caractérisations de modèles à base d'analogies pour l'apprentissage automatique des langues naturelles[END_REF]; [START_REF] Stroppa | Du quatrième de proportion comme principe inductif : une proposition et son application à l'apprentissage de la morphologie[END_REF], for the following tasks: (i) grapheme-to-phoneme conversion, (ii) inflectional analysis of word forms, and (iii) derivational analysis of word forms. In the first task, inputs and outputs are strings (sequences of graphemes and phonemes). In the second one, we look for the lemma and the morphological features associated to a given word form; inputs are strings and outputs are pairs of string and (flat) feature structures. The goal of the third task is to find the hierarchical decomposition of a wordform into morphemes; inputs are strings and outputs are labeled trees. These experimental results show that state-of-the-art performances can be achieved for these three tasks.

Perspectives

The work reported in this paper has deliberately concentrated on the computation of proportions: this is, of course, only half of the story and a lot of efforts are required to put these algorithms to use in realistic machine learning applications. This aspect of the work is still on-going, even if promising results have been obtained in a variety of applications and for various languages (see the references cited above).

Current development is active on two separate fronts. On the experimental front, we intend to widen the range of applications of analogical learning, by considering more language types (especially languages exhibiting complex and/or non concatenative morphological phenomena), and by considering novel natural language processing tasks, such as, for instance, word sense disambiguation, which seems to be a promising test-bed for analogical approaches (see the discussion in [START_REF] Pirrelli | The hidden dimension: paradigmatic approaches to data-driven natural language processing[END_REF] and the references cited therein).

On the more theoretical front, the main computational burden of a machine learning approach based on analogical proportions remains the search, in the database of known instances, of candidate analog triples on which to ground the inference procedure. A brute force approach would require to evaluate a number of proportions that grows as the cube of the number of training instances, which, given the complexity of the algorithms discussed in this paper, and the typical size of dictionaries or tree-banks, is prohibitive. We believe that the search step could be made considerably faster if we could somehow restrict this search to a subset of promising triples. In other terms, what we need are procedures allowing to rank candidates based on some numerical scores. Propositions for defining a gradual notion of analogical proportions have been made in [START_REF] Yvon | Solving analogies on words[END_REF] and our next step will be to reevaluate these propositions and see how they can help improve the search procedure.

An Algorithmic Vision of Analogical Proportions

As a concluding note, we would finally like to emphasize the relationship between our work and some conceptions of analogical proportions that are prevalent in some Artificial Intelligence (AI) circles. In particular, we would like to show that our framework can be extended to take into account more complex proportions, such as those studied in AI.

In our framework, proportions are mainly based on the notions of decomposition and alternation (cf. Section 3). This is suited to the "simple" case of semigroup and its derivatives, where only one operator is available. However, two directions have already been explored, which enhance the expressiveness of the approach: (i) the use of multi-level proportions, which stack structures recursively, and (ii) the addition of operators, which enrich the composition mechanism; these kinds of extensions have been introduced to handle languages (cf. Section 4.2) and have also proved necessary to handle the case of trees (cf. Section 5).

By using unrestricted operators and unlimited recursive schemes, we are actually heading towards a situation where proportions can be defined for any computable objects. The decomposition of an object is simply an algorithmic procedure computing this object: u(x 1 , . . . , x n ) = x is an "algorithmic factorization" u x of x, where u is an algorithm and x 1 , . . . , x n some parameters. By convention, we will note u x (0) = u and ∀i ∈ 1, n , u x (i) = x i . A definition of analogical proportion which applies to any computable object can be derived from these considerations.

Definition 16 (Analogical proportions between computable objects).

For a quadruple (x, y, z, t), we have x : y :: z : t if and only if there exist four algorithmic factorizations u x , u y , u z , u t of x, y, z, and t respectively, such that:

∀i ∈ 0, n , (u y (i), u z (i)) ∈ {(u x (i), u t (i)), (u t (i), u x (i))}
This definition is completely general and consistent with the work of [START_REF] Schmid | An algebraic framework for solving proportional and predictive analogies[END_REF]. It can also be used to model complex analogies: most of the examples studied by Hofstadter & the Fluid Analogies Research Group (1995) can be expressed in this framework. For example, in order to model abc : abd :: ijk : ijl, it is sufficient to write u(a 1 , a 2 , a 3 , a 4 ) = a 1 .a 2 .(a 3 + a 4 ), which yields:

u(a, b, c, 0) = abc, u(a, b, c, 1) = abd, u(i, j, k, 0) = ijk, u(i, j, k, 1) = ijl.
The relationship between the letters a, b, and c can also be exploited: if we note u(a 1 , a 2 ) = a 1 .(a 1 + 1).(a 1 + 2 + a 2 ), we have u(a, 0) = abc, u(a, 1) = abd, u(i, 0) = ijk, u(i, 1) = ijl.

This also applies to proportions such as abc : abd :: mrrjjj : mrrkkk.

The algorithms used in the case of strings (cf. Section 3.4), are very simple: they can only concatenate strings. The less strings they are concatenating, the less complex they are considered (cf. notion of degree), and better is the proportion. In the algorithmic context, the (Kolmogorov) algorithmic complexity (as described e.g. by [START_REF] Li | An Introduction to Kolmogorov Complexity and its Applications[END_REF]) seems to be a reasonable criterion to qualify a proportion:22 the less complex the algorithms involved in proportion, the better the proportion, and the more likely this proportion will match the intuition. In other words, we have recasted the problem of recognizing and verifying analogies into the problem of finding algorithms with small complexities. We do not plan to develop our work along those lines any further and intend to continue focusing on those specific structures that are commonly used in NLP applications; it is however comforting to realize that our work is consistent with general purpose, cognitively-oriented visions of analogical proportions.

A Proof of Proposition 10

Proof. Let x : y :: z : t be an analogical proportion with D = D(x : y :: z : t), O = O (x : y :: z : t, x) and D > O > 1.

By hypothesis, there exist some factorizations (f x , f y , f z , f t ) of size n and an interval J = i, j such that f x (J) = , | J | = O and for all interval I ⊆ 1, n with | I | > O, f x (I) = . Since D > O, one factor in x is not empty and we have either i > 1 or j < D. For symmetry reasons, we can assume without loss of generality that i > 1. The proof is achieved by building new factorizations of x, y and z obtained by permuting the factors at position i and i + 1 in x, y and z. For α ∈ {x, y, z, t}, we define

fα (k) = f α (k) if k < i -1, fα (i -1) = f α (i -1)f α (i + 1), fα (i) = f α (i), fα (k) = f α (k + 1) if i < k < D.
Since | J | > 1, we have i + 1 ∈ J and f x (i + 1) = . Moreover, for symmetry reasons, we can assume that (f x (i), f t (i)) = (f y (i), f z (i)) and (f x (i + 1), f t (i + 1)) = (f z (i + 1), f y (i + 1)). In particular, since f x (i) = f y (i) = and f x (i + 1) = f z (i + 1) = , we have f α (i + 1)f α (i) = f α (i -1)f α (i) for α ∈ {x, y, z}, and permuting these chunks yields proper factorizations of x, y and z. The result of this construction is a factorization ft for a word t such that x : y :: z : t with D(x : y ::

z : t) = | fx | = | f x | -1 = D -1.
Moreover, the "local" degree of these new factorizations has decreased by 1, so the equality O (x : y :: z : t, x) = O (x : y :: z : t, x) -1 is obtained by applying the same permutations for all the intervals J such that f x (J) = and | J | = O.

Finally, since (f x (i), f t (i)) = (f y (i), f z (i)) with f x (i) = f y (i) = and (f x (i + 1), f t (i + 1)) = (f z (i + 1), f y (i + 1)) with f x (i + 1) = f z (i + 1) = , we have

max(| f x (i -1) |, | f t (i -1) |) + max(| f x (i) |, | f t (i) |) + max(| f x (i + 1) |, | f t (i + 1) |) = max(| f x (i -1) |, | f t (i -1) |) + | f z (i) | + | f y (i + 1) | ≤ max(| f x (i -1) |, | f t (i -1) | + | f y (i + 1) |) + | f z (i) |,

which yields

T (x : y :: z : t) ≤ T (x : y :: z : t).

B Proof of Proposition 12

In the following, we show that, for a tree t, the Algorithm 1 constructs an automaton A t such that the successful paths in A t are exactly the P -factorizations of t.

Let us first remark that the set of nodes P os(t) of a tree t is equipped with a natural partial order23 ≤ defined as follows: ∀(p i , p j ) ∈ P os(t) 2 , p i ≤ p j if and only if ∃p ∈ N * such that p i = p j .p. This simply states that p i ≤ p j if and only if p i is a descendant of p j , i.e. p j dominates p i . An antichain with respect to this partial order is a subset a ∈ P os(t) in which each pair of elements is incomparable, that is: ∀(x, y) ∈ a 2 , neither x ≤ y nor y ≤ x (no node is dominating another node). Given an antichain a = {p 1 , . . . , p n } of P os(t), replacing the subtrees rooted at (p 1 , . . . , p n ) in t with the variables (p 1 , . . . , p n ) results in a tree t such that VPos(t ) = a.24 Moreover, the application VPos is defined for any such t ; VPos is thus bijective. For readability, VPos is noted γ in the following. Lemma 2. A bijective correspondence can be established between any P -factorization [(t 1 , . . . , t n ), (p 1 , . . . , p n-1 )] of a tree t and the sequence of antichains (a 1 , . . . , a n ) defined as ∀i ∈ 1, n , a i = γ(t 1 v1 . . . vi-1 t i-1 ). This sequence verifies a n = ∅, and ∀i ∈ 1, n , a i+1 = a i \ {p i } ∪ p i .γ(t i ).

Proof. Let [(t 1 , . . . , t n ), (p 1 , . . . , p n-1 )] be a P -factorization of t. We note for i in 1, n , t i = t 1 v1 . . . vi-1 t i-1 . The tree t i+1 is obtained by replacing in t i the variable p i at position p i with t i . It is thus routine to verify that γ(t i+1 ) = γ(t i )\{p i }∪p i .γ(t i ), and γ(t n ) = γ(t) = ∅.

Conversely, let (a 1 , . . . , a n ) be a sequence of antichains such that a n = ∅, and for i ∈ 1, n , there exists a position p i and a tree t i with a i+1 = a i \ {p i } ∪ p i .γ(t i ). For i ∈ 1, n , we set and t i = γ -1 (a i ). We have ∀i ∈ 1, n , t i+1 = t i pi t i , and t n = γ -1 (∅) = t, so [(t 1 , . . . , t n ), (p 1 , . . . , p n-1 )] defines a P -factorization of t. Lemma 3. Let A t = Q, E, i, f =ConstructAutomaton(t). There exists a bijection β from the set of states Q to the set of antichains over P os(t) such that β(i) = { }, β(f ) = ∅, and (q 1 , q 2 , p 1 → t 1 ) ∈ E if and only if a 2 = a 1 \ {p 1 } ∪ p 1 .γ(t 1 ), where a 1 = β(q 1 ), a 2 = β(q 2 ).

Proof. By induction on the size of the tree. Let us consider the tree t = l(t 1 , . . . , t n ) of size s t . If s t = 1, the only antichains of t are a 1 = { } and a 2 = ∅, which correspond exactly to the two states of the automaton constructed by ConstructAutomaton(t) (respectively i and f ). The variable in γ -1 (a 1 ) can rewrite either to itself or to l; these are the two transitions in E, which proves the result for s t = 1 (see Lines 1-4).

We now assume the result is true for any tree of size s < s t . Let a be an antichain of t; by definition of an antichain, either a = { } or / ∈ a. The first case correspond to the initial state, added to the set of states (Line 5). In the second case, since / ∈ a, a can be rewritten as a = 1.a 1 ∪ • • • ∪ n.a n , where a i is an antichain of t i for i ∈ 1, n . Conversely, if a i is an antichain of t i for i ∈ 1, n , 1.a 1 ∪ • • • ∪ n.a n defines an antichain of a such that / ∈ a. By induction hypothesis, there exists a bijection between the antichains of P os(t i ) and the states of ConstructAutomaton(t i ). Consequently, there is also a bijection between the antichains of P os(t) and the states of ConstructAutomaton(t) (Lines 7-11).

A replacement in t of variable i.p with a tree u at position i.p, with i ∈ 1, n , corresponds to a replacement in t i of variable p with a tree u at position p such that u = add_pref(i, u), and vice-versa, so by induction hypothesis, the required property over the transitions is verified (Lines 12-15). A replacement in an empty tree of the variable with a tree u corresponds to a transition from the initial state i to the state q such that γ(u) = q (Lines 6 and 16), which ends the proof.

Proof. Finally, to prove that the successful paths in A t are exactly the P -factorizations of t, it is sufficient to note that the P -factorizations exactly correspond to the sequences of antichains that verify certain conditions (Lemma 1), and that these very sequences of antichains correspond to the sucessful paths in A t (Lemma 2).

C Implementation Details

The general algebraic analogical framework presented in this paper has been partly implemented in a software package called ALANIS (A Learning-b ANalogy Inferencer for Structured data). The goal of this implementation is to make concrete the mathematical foundations by furnishing the algorithms needed to compute analogical proportions. Moreover, we want these algorithms to work on the large variety of structures covered by the formal model.

In order to achieve this goal of genericity, our implementation is based on the design-pattern underlying the Vaucanson library [START_REF] Lombardy | Introducing Vaucanson[END_REF]. This designpattern has first been conceived to manipulate generalized automata, i.e. automata whose transitions may be labeled by letters, but also words or series [START_REF] Sakarovitch | Éléments de théorie des automates[END_REF]. The great particularity of this design-pattern is to completely separate the algebraic structures (e.g. alphabets, monoids, semirings and series) from their implementations (e.g. characters, strings, vectors or maps). This genericity heavily relies on static-linking techniques which ensure that the framework does not suffer from runtime overhead (Régis-Gianas & Poss, 2003).

This design-pattern forms the core of our framework: the algebraic structures (which give a meaning to analogical proportions) and their concrete implementations are totally separated. For example f loat or double may be used to modelize elements of (R, +) or (R * , ×) and integers may be used to modelize elements of (Z, +). In every case, the underlying algebraic structure is an abelian group and there is a single algorithm to handle all these situations. Moreover, it is possible to specialize an algorithm with respect to its implementation: additional optimizations can be performed when the underlying implementation of a data structure has some features we can take advantage of while preserving the framework core.

Figure 1 :

 1 Figure1: Analogical proportion between syntactic trees (adapted from[START_REF] Matthews | Morphology[END_REF]).

Figure 2 :

 2 Figure 2: Analogical proportion between logical representations.

Figure 5 :Figure 6 :

 56 Figure 5: Mare and cows, again!

  Figure 8: A parallelogram.

Figure 9 :

 9 Figure 9: Feature structure representing the verb form loves.

Figure 10 :

 10 Figure 10: Feature structure representing the dependency graph of a sentence.

Figure 11 :

 11 Figure 11: The transducer T w computing complementary sets with respect to w.

Corollary 1 .

 1 If t is a solution of the equation x : y :: z :? with D(x : y :: z : t) > O (x : y :: z : t, x) > 1, then there exists a solution t such that O (x : y :: z : t, x) = 1.

Figure 14 :

 14 Figure 14: Analogical proportion between languages.

Σ:

  : z : t in the following. For example, since reading : reader Σ :: reviewing : reviewer, we have (over 2 Σ ): {reading} : {reader} :: {reviewing} : {reviewer}.

  which yields: ∀k ∈ 1, m , {a i } : {a i } W :: {b i } : {b i }. Proposition 11. ∀(x, y, z, t) ∈ (2 Σ ) 4 , x : y W :: z : t⇔x : y S :: z : t. Proof. ⇒. By induction on the degree of the proportion. Let (x, y, z, t) ∈ (2 Σ ) 4 with x : y W :: z : t and d = D(x : y W :: z : t) the degree of the proportion. By definition, there exist some languages:

S:

  : z : t and d = D(x : y S :: z : t) the degree of the proportion. If d = 1, then the result is trivial since A(2 Σ ) ⊆ B(2 Σ ).

Figure 16 :

 16 Figure 16: The result t 3 of the substitution t 1 x t 2 .

Figure 17 :

 17 Figure 17: military : demilitarization :: colony : decolonization (with implicit (a) and explicit (b) factorizations).

Figure 19 :

 19 Figure 19: From tree (a) to automaton (b). The transitive closure of the transition relation and loops in the automaton have been omitted for clarity.

C:

  : z : t ⇒ p(x) : p(y) :: p(z) : p(t).

C:

  : z : t ⇒ ab(x) : ab(y) :: ab(z) : ab(t).

  j k=1,l=1 {α 1k α 2l }.

	Since ∀k ∈ 1, i , x 1k : y 1k

Σ

:: z 1k : t 1k and ∀k ∈ 1, j , x 2k : y 2k Σ :: z 2k : t 2k , we also have ∀(k, l) ∈ 1, i × 1, j , x 1k x 2l : y 1k y 2l Σ :: z 1k z 2l : t 1k , which completes the proof that the proportion x : y W :: z : t holds.

  u xi : u yi :: u zi : u ti . By definition, there exist four factorizations[s x , v], [s y , v], [s z , v], [s t , v] of x,y, z, and t respectively, such that:

	Let (x, y, z, t) ∈ (T (U )) 4 such that x : y

C

:: z : t.

These proportions correspond to the Aristotelian (Aristote) notion of Analogy.

This notion has also been invoked in the field of syntax[START_REF] Bloomfield | Le Langage[END_REF][START_REF] Itkonen | A rehabilitation of analogy in syntax (and elsewhere)[END_REF][START_REF] Lavie | Le locuteur analogique ou la grammaire mise à sa place[END_REF], even though the use of analogy in this domain has been limited by the generative claims about the "inadequacy" and "unclarity" of this notion[START_REF] Chomsky | The logical structure of linguistic theory[END_REF].

This kind of equation is also termed computation of the fourth (proportional) term[START_REF] De | Cours de linguistique générale[END_REF] or analogical deduction[START_REF] Blevins | Word-based morphology[END_REF].

These works, and others, have also been used to support the view that some of the cognitive processes involved in the recognition of words, or in the letter-to-sound mapping, could be modeled through some kinds of analogical process. We will not address here the cognitive plausibility of analogy-based language processing, but rather concentrate on the algorithmic aspects of the computation of proportion.

This tool relies on the automata library VAUCANSON[START_REF] Lombardy | Introducing Vaucanson[END_REF], which makes use of generic programming and static polymorphism(Régis-Gianas & Poss, 2003), allowing for both adaptability and efficiency.

Let us assume that we want to find the morphological analysis M (dearly) of the unknown word form dearly. In this case, the misleading proportion ear : early :: dear : dearly is actually not a problem for the analogical learners mentioned in the Introduction. Indeed, the resolution procedure, whose goal is to find a solution to the analogical equation M (ear) : M (early) :: M (dear) :?, will fail (this equation between morphological features has no solution), and no analysis will be proposed based on this proportion.

A (semigroup) morphism M from (U, ⊕) to (V, ) is a mapping such that ∀x, y ∈ U, M (x ⊕ y) = M (x) M (y).

For a multiset (S, m), we can also extend m to a set U ⊇ S, by setting m(e) = 0, ∀e ∈ U \ S.

Some linguistic theories make also use of other types of complex feature values, such as lists or sets.

Note that this result is directly derived from proposition 1, since the length application is a semigroup morphism from the set of words Σ to the set of integers N.

It is possible to build the intersection product of two automata in such a way that all the states in the product are accessible[START_REF] Sakarovitch | Éléments de théorie des automates[END_REF]. In this case, checking for emptiness simply amounts to verifying that the set of final states is not empty, which is done in constant time.

Since atomic proportions have served as a basic component of our formalism, it seems reasonable to impose A(U ) ⊆ B(U ); this is the reason why A(2 Σ ) is explicitly added to B(2 Σ ).

Since the multiplication (⊗) with the identity element for ⊕ is an absorbing (thus destructive) operation, we additionally impose that this identity element cannot be involved in a multiplication.

This is legitimate by virtue of the fact, as pointed out in Section 4.2.2, that the factors composed using concatenation are non-empty.

The number of factorizations (with respect to union) of a given language is actually infinite since a factor can be repeated an unlimited number of times. However, if we have proportions in mind, it is clear that it is not necessary to repeat a term more than twice: in a proportion x : y :: z : t, a factor in x can only be aligned with a factor in y, in z, or in both. For a given language, the number of factorizations that are relevant to proportions is thus finite.

Each state q can be associated to a tree, which is the result of the applications of the substitutions leading to q; γ -1 (q) denotes this tree. See Appendix B for a formal and detailed explanation.

A proportion between trees involves substitutions that rewrite the same variables at the same time. Consequently, when looking for proportions, N -factorizations, in which variables are represented by their positions in the factorization, are more adapted than P -factorizations, in which variables are represented by their positions in the trees. However, it is more difficult to express the set of N -factorizations in an efficient way than it is for P -factorizations, hence the introduction of the two steps in our approach. First, candidate factorizations are extracted from a compact representation of the set of P -factorizations, then a consistency check on variables is performed.

For a definition of the notion of an antichain, see the proof in Appendix B.

The concatenation operation is explicitly noted for readability.

This software is freely available from http://www.computing.dcu.ie/~nstroppa/index. php?page=softwares.

Describing objects thanks to the algorithms that can generate them is the basis of the algorithmic complexity.

Trees can indeed be defined as particular partially ordered sets.

The so-called frontier operation in the Data-Oriented Parsing litterature.