Ordres libres

La méthodologie de formalisation linguistique adoptée dans le chapitre précédent permet de produire aisément des linéarisations vers la forme canonique des phrases dans les langues où l’ordre des mots est fixé. Toutefois, elle échoue à représenter de manière concise l’ensemble des réalisations de surface possibles dans des langues offrant un plus grand degré de liberté sur l’ordre des syntagmes. Il est donc nécessaire, pour linéariser nos structures abstraites vers leur forme phonologique, de proposer des réalisations multiples, couvrant l’ensemble des combinaisons possibles. Afin de condenser ces descriptions, nous proposons dans ce chapitre une représentation intermédiaire, qui décrit des phrases modulo permutation de certains de leurs composants. Par suite, nous proposons plusieurs classes de langages s’appuyant sur cette représentation, et étudions la complexité algorithmique de plusieurs problèmes liés à l’analyse d’un énoncé selon ces représentations. 5.1 Motivation La classe de phénomènes linguistiques que nous souhaitons modéliser, désignés par la suite sous le terme d’ordres libres, recouvre plusieurs notions. La plus évidente est la reconnaissance de phrases dans des langues à déclinaisons, où un marquage morphologique des cas (nominatif, accusatif, datif, etc.) est systématiquement présent et permet de retrouver la fonction syntaxique des arguments, indépendamment de leur position relative dans la phrase ; de telles langues, à l’image du latin, peuvent disposer d’un ordre canonique des arguments, mais autorisent fréquemment de larges déviations de cet ordre, sans affecter la grammaticalité ou le sens fondamental de la phrase [cf. Marouzeau, 1922]. Toutefois, le concept d’ordres libres peut également recouvrir des phénomènes plus restreints dans des langues imposant normalement des contraintes sur l’ordre de leurs arguments. Ainsi, les propositions subordonnées imbriquées en allemand sont usuellement construites de façon « parenthésée », en plaçant 113 Ordres libres 5.1. Motivation les arguments nominaux du verbe au début, le verbe à la fin, et la proposition subordonnée entre les deux. Cependant, certains exemples attestent qu’il est possible, en préservant l’ordre des verbes à la fin, de mélanger librement leurs arguments, sans respecter le parenthésage induit par la structure abstraite. La reconstruction exacte de la structure syntaxique de ces énoncés (notamment les relations entre les verbes et leurs arguments) s’appuie alors usuellement sur des considérations sémantiques et pragmatiques. Un premier exemple issu de Haider [1991] et repris dans Becker et al. [1992] est illustré par la figure 5.1. Dans cet exemple, les différents arguments de la proposition subordonnée forment des blocs, dont l’ordre relatif est quelconque : seule la position du verbe (rejeté à la fin) est constante. Un second exemple, tiré de Becker et al. [1991] et donné dans la figure 5.2, illustre la possibilité de mélanger les arguments issus de plusieurs propositions subordonnées imbriquées. L’exemple comporte trois propositions subordonnées imbriquées, qui sont construites dans l’ordre canonique en haut de la figure : le placement de leurs arguments est toutefois libre, et indépendant de l’ordre (fixé) des verbes figurant à la fin, lequel permet de déduire la structure de la phrase. Observons que cette liberté permet de mélanger entre eux des composants appartenant à plusieurs propositions distinctes.Notre objectif dans la suite de ce chapitre est de proposer une modélisation des phénomènes d’ordre libre, qui décrive de manière complèteme uniforme l’ensemble des ordres des mots autorisés par une langue ou par un phénomène donné. Cette modélisation exclut donc la possibilité de traiter des nuances de sens et d’emphase véhiculées par le choix d’un ordre en particulier de préférence à un autre. Tous les phénomènes offrant un degré modéré de liberté dans l’ordre des mots ne seront pas descriptibles par l’outil que nous proposons : ainsi, nous ne pourrons pas proposer de représentation unique pour toutes les réalisations d’une proposition indépendante en allemand, où le verbe doit obligatoirement occuper la seconde position, mais où le placement de ses arguments est libre. Choisi pour ses propriétés algorithmiques, cet outil permet seulement de rendre compte d’un placement séquentiel entre les syntagmes (comme dans une grammaire de réécriture classique) ou de leur permutation libre, c’est à dire sans contrainte aucune entre leurs positions respectives. En dépit de cette limitation, il semble néanmoins adéquat pour modéliser simplement la grammaticalité de langues comme le latin, ou pour factoriser partiellement des réalisations équivalentes dans des langues comme l’allemand. 

L’algèbre Comm(Σ) 

Mots commutatifs Nous introduisons maintenant la notion de mots modulo permutations, ou mots commutatifs sur un alphabet, qui sera le support de notre représentation des ordres libres. Ces mots commutatifs sont formés soit comme des mots usuels, par la concaténation successive de leurs lettres ; soit comme des mots libres dont les composants peuvent être lus indifféremment dans n’importe quel ordre. L’ensemble des mots commutatifs sur un alphabet est défini à partir des lettres de cet alphabet, d’une opération binaire de concaténation, et d’une autre opération binaire de composition libre, qui permet d’assembler des mots commutatifs sans spécifier leur ordre de lecture. Définition 5.1. L’ensemble Comm(Σ) des mots commutatifs construits sur un alphabet Σ est l’ensemble des termes de l’algèbre suivante : — Le mot vide ε est un terme de Comm(Σ). — Tout élément l ∈ Σ est un terme de Comm(Σ). — L’opération binaire  (concaténation) est associative. — L’opération binaire ⊗ (composition libre) est associative/commutative. Les termes de Comm(Σ) peuvent représenter de façon abstraite des phrases, dans lesquelles l’ordre de certains composants est laissé libre. Remarquons que tout terme construit sans utiliser l’opération ⊗ s’interprète de façon transparente comme un mot de Σ ∗ : l’opération  est identique à la concaténation usuelle. Notion d’équivalence Les propriétés des opérations  et ⊗ (associativité et commutativité) décrivent une notion d’équivalence entre les termes de Comm(Σ), sur laquelle nous nous appuierons fortement par la suite. En particulier, deux termes sont équivalents si la seule chose qui les distingue est l’ordre des arguments d’une composition libre. Définition 5.2. Deux termes t, t0 ∈ Comm(Σ) sont dits immédiatement équivalents si et seulement si l’une de ces trois conditions est vérifiée : — t = C[((t1, t2), t3)] et t 0 = C[(t1, (t2, t3))] (associativité de ) — t = C[⊗(⊗(t1, t2), t3)] et t 0 = C[⊗(t1, ⊗(t2, t3))] (associativité de ⊗) — t = C[⊗(t1, t2)] et t 0 = C[⊗(t2, t1)] (commutativité de ) La figure 5.3 illustre cette définition. Par extension, l’équivalence de t et t 0 , notée t ≡c t 0 , est définie comme la clôture réflexive, symétrique et transitive de cette relation. Dans la suite, la notion d’équivalence issue de l’associativité de  sera d’une importance réduite : l’équivalence entre (ab)c et a(bc), dénotant tous deux l’unique mot abc ne revêt pas d’importance particulière. En revanche, la combinaison de l’associativité et de la commutativité de ⊗ permettent de choisir librement l’ordre des composants d’un mot : ainsi, les termes (a⊗b)⊗c et a ⊗ (c ⊗ b) sont équivalents, matérialisant le fait que les mots abc et acb résultent tous deux de la composition libre des trois lettres a, b et c. 

Langage d’un mot commutatif 

Nous définissons maintenant la notion de langage d’un terme de Comm(Σ) : il s’agit de l’ensemble des mots sur l’alphabet Σ pouvant être obtenus en choisissant un ordre linéaire quelconque pour les opérations de composition libre. Ces ordres peuvent être obtenus en faisant jouer les propriétés d’associativité et de commutativité de ⊗, puis en lisant simplement les feuilles des termes résultants de gauche à droite. 

Définition 

La frontière (ou yield) frt(t) d’un terme t ∈ Comm(Σ) est définie comme le mot de Σ ∗ obtenu en concaténant les feuilles de t de gauche à droite : — frt(ε) = ε — frt(l) = l pour tout l ∈ Σ — frt((t1, t2)) = frt(t1). frt(t2) — frt(⊗(t1, t2)) = frt(t1). frt(t2) Le langage L(t) d’un terme t est défini comme l’ensemble des frontières des termes équivalents à t : L(t) = {frt(t 0 ) | t 0 ≡c t}. Cette définition traduit la notion qu’un mot commutatif correspond à un ensemble de mots, formé de tous les choix possibles entre ses composants librement ordonnés. Une conséquence immédiate est que le langage d’un terme est fini, et que sa taille est bornée exponentiellement par la taille du terme dans le pire des cas. La figure 5.4 exemplifie la notion de langage d’un terme en listant les différentes permutations d’un terme représentant une phrase latine.