Ce mémoire d'Habilitation à Diriger des Recherches est organisé en deux tomes. Le Tome I a pour but de présenter les travaux de recherche effectués durant ma carrière d'enseignant-chercheur (quatorze articles publiés dans des revues internationales avec comité de lecture). Les textes intégraux de ces articles sont réunis dans le Tome II.

Cette thèse présente une étude dans divers domaines de l'informatique théorique de modèles de calculs combinant automates finis et contraintes arithmétiques. Nous nous intéressons aux questions de décidabilité, d'expressivité et de clôture, tout en ouvrant l'étude à la complexité, la logique, l'algèbre et aux applications. Cette étude est présentée au travers de quatre articles de recherche. Le premier article, Affine Parikh Automata, poursuit l'étude de Klaedtke et Ruess des automates de Parikh et en définit des généralisations et restrictions. L'automate de Parikh est un point de départ de cette thèse; nous montrons que ce modèle de calcul est équivalent à l'automate contraint que nous définissons comme un automate qui n'accepte un mot que si le nombre de fois que chaque transition est empruntée répond à une contrainte arithmétique. Ce modèle est naturellement étendu à l'automate de Parikh affine qui effectue une opération affine sur un ensemble de registres lors du franchissement d'une transition. Nous étudions aussi l'automate de Parikh sur lettres: un automate qui n'accepte un mot que si le nombre de fois que chaque lettre y apparaît répond à une contrainte arithmétique. Le deuxième article, Bounded Parikh Automata, étudie les langages bornés des automates de Parikh. Un langage est borné s'il existe des mots w_1, w_2, ..., w_k tels que chaque mot du langage peut s'écrire w_1...w_1w_2...w_2...w_k...w_k. Ces langages sont importants dans des domaines applicatifs et présentent usuellement de bonnes propriétés théoriques. Nous montrons que dans le contexte des langages bornés, le déterminisme n'influence pas l'expressivité des automates de Parikh. Le troisième article, Unambiguous Constrained Automata, introduit les automates contraints non ambigus, c'est-à-dire pour lesquels il n'existe qu'un chemin acceptant par mot reconnu par l'automate. Nous montrons qu'il s'agit d'un modèle combinant une meilleure expressivité et de meilleures propriétés de clôture que l'automate contraint déterministe. Le problème de déterminer si le langage d'un automate contraint non ambigu est régulier est montré décidable. Le quatrième article, Algebra and Complexity Meet Contrained Automata, présente une étude des représentations algébriques qu'admettent les automates contraints et les automates de Parikh affines. Nous déduisons de ces caractérisations des résultats d'expressivité et de complexité. Nous montrons aussi que certaines hypothèses classiques en complexité computationelle sont reliées à des résultats de séparation et de non clôture dans les automates de Parikh affines. La thèse est conclue par une ouverture à un possible approfondissement, au travers d'un certain nombre de problèmes ouverts. / This thesis presents a study from the theoretical computer science perspective of computing models combining finite automata and arithmetic constraints. We focus on decidability questions, expressiveness, and closure properties, while opening the study to complexity, logic, algebra, and applications. This thesis is presented through four research articles. The first article, Affine Parikh Automata, continues the study of Klaedtke and Ruess on Parikh automata and defines generalizations and restrictions of this model. The Parikh automaton is one of the starting points of this thesis. We show that this model of computation is equivalent to the constrained automaton that we define as an automaton which accepts a word only if the number of times each transition is taken satisfies a given arithmetic constraint. This model is naturally extended to affine Parikh automata, in which an affine transformation is applied to a set of registers on taking a transition. We also study the Parikh automaton on letters, that is, an automaton which accepts a word only if the number of times each letter appears in the word verifies an arithmetic constraint. The second article, Bounded Parikh Automata, focuses on the bounded languages of Parikh automata. A language is bounded if there are words w_1, w_2, ..., w_k such that every word in the language can be written as w_1...w_1w_2...w_2 ... w_k...w_k. These languages are important in applications and usually display good theoretical properties. We show that, over the bounded languages, determinism does not influence the expressiveness of Parikh automata. The third article, Unambiguous Constrained Automata, introduces the concept of unambiguity in constrained automata. An automaton is unambiguous if there is only one accepting path per word of its language. We show that the unambiguous constrained automaton is an appealing model of computation which combines a better expressiveness and better closure properties than the deterministic constrained automaton. We show that it is decidable whether the language of an unambiguous constrained automaton is regular. The fourth article, Algebra and Complexity Meet Constrained Automata, presents a study of algebraic representations of constrained automata and affine Parikh automata. We deduce expressiveness and complexity results from these characterizations. We also study how classical computational complexity hypotheses help in showing separations and nonclosure properties in affine Parikh automata. The thesis is concluded by a presentation of possible future avenues of research, through several open problems.

À l’ère du militantisme digital, il est fréquent d’apercevoir des militants se placer en tant que porte parole sur différents champs de bataille au fil du temps. Dans ce contexte, la légitimité de leurs prises de position est questionnée par le tribunal médiatique. Là où certains dénoncent un opportunisme politique, nous avançons la thèse selon laquelle une multitude d’éléments peuvent motiver les changements de champs d’action militants visibles. C’est pourquoi la recherche présentée vise à mettre en lumière les processus influençant les transitions d’engagements militants au travers des mouvements sociaux protestataires. Pour ce faire, des entretiens semi-directifs ont été menés auprès de 8 militants alors actifs au sein de la mouvance opposée aux mesures sanitaires. Dans cette démarche, le récit des participants et un calendrier de vie ont été combinés dans un protocole d’enquête narrative biographique. Finalement, les données d'entretiens collectées ont été analysées à l'aide d'une méthode de théorisation ancrée s'appuyant sur un cadre théorique mobilisant la perspective du parcours de vie. Cette méthode a permis de montrer que les expériences influençant les trajectoires militantes diffèrent selon les modalités de transitions ; c’est-à-dire selon si elle s’effectue entre des groupes contestataires au sein d’un même mouvement, ou entre des mouvements défendant des causes différentes. Les résultats ont montré que les transitions d’engagements entre groupes contestataires peuvent être influencées par des insatisfactions liées aux stratégies d’actions ; alors que les transitions d’engagement actif entre deux mouvements protestataires peuvent être expliquées, soit (a) par un cumul d’engagement survenu suite à l’apparition d’un événement imprévu induisant une priorité d’action, soit (b) par une stratégie visant à faire perdurer les rétributions de la carrière militante au moment du déclin du mouvement alors investi. Par ailleurs, ce projet de recherche contribue plus généralement à expliquer les expériences ayant motivé des transitions d’engagements militants selon les propos des acteurs de cet objet d’études, dont 5 leaders du mouvement opposé aux mesures sanitaires. / In the age of digital activism, it's common to see activists positioning themselves as spokespersons on different battlefields over time. In this context, the legitimacy of their positions is questioned by the media tribunal. Where some denounce political opportunism, we put forward the thesis that a multitude of elements can motivate visible changes in activist fields of action. For this reason, the research presented here aims to shed light on the processes influencing transitions in activist commitment through social protest movements. To this end, semi-directive interviews were conducted with 8 activists then active within the movement opposed to health measures. In this approach, the participants' narratives and a life calendar were combined in a biographical narrative survey protocol. Finally, the interview data collected were analyzed using a grounded theorizing method based on a theoretical framework mobilizing the life-course perspective. This method enabled us to show that the course influencing militant trajectories differs according to the modalities of transitions, i.e. whether they take place between protest groups within the same movement, or between movements defending different causes. The results show that transitions of commitment between protest groups can be influenced by dissatisfaction with action strategies ; whereas transitions of active commitment between two protest movements can be explained either (a) by an accumulation of commitment following the appearance of an unforeseen event inducing a priority for action, or (b) by a strategy aimed at maintaining the rewards of the activist career at the time of the decline of the movement then invested. In addition, this research project contributes more generally to explaining the experiences that motivated militant transitions in activist commitments according to the words of the actors in this object of study, including 5 leaders of the movement opposed to health measures.

Dans ces travaux, nous explorons comment les techniques de Générations Automatiques de Langue Naturelle (GLN) peuvent être utilisées pour aborder la tâche de génération (semi-)automatique de matériel et d'activités dans le contexte de l'apprentissage de langues assisté par ordinateur. En particulier, nous montrons comment un Réalisateur de Surface (RS) basé sur une grammaire peut être exploité pour la création automatique d'exercices de grammaire. Notre réalisateur de surface utilise une grammaire réversible étendue, à savoir SemTAG, qui est une Grammaire d'Arbre Adjoints à Structure de Traits (FB-TAG) couplée avec une sémantique compositionnelle basée sur l'unification. Plus précisément, la grammaire FB-TAG intègre une représentation plate et sous-spécifiée des formules de Logique de Premier Ordre (FOL). Dans la première partie de la thèse, nous étudions la tâche de réalisation de surface à partir de formules sémantiques plates et nous proposons un algorithme de réalisation de surface basé sur la grammaire FB-TAG optimisé, qui supporte la génération de phrases longues étant donné une grammaire et un lexique à large couverture. L'approche suivie pour l'optimisation de la réalisation de surface basée sur FB-TAG à partir de sémantiques plates repose sur le fait qu'une grammaire FB-TAG peut être traduite en une Grammaire d'Arbres Réguliers à Structure de Traits (FB-RTG) décrivant ses arbres de dérivation. Le langage d'arbres de dérivation de la grammaire TAG constitue un langage plus simple que le langage d'arbres dérivés, c'est pourquoi des approches de génération basées sur les arbres de dérivation ont déjà été proposées. Notre approche se distingue des précédentes par le fait que notre encodage FB-RTG prend en compte les structures de traits présentes dans la grammaire FB-TAG originelle, ayant de ce fait des conséquences importantes par rapport à la sur-génération et la préservation de l'interface syntaxe-sémantique. L'algorithme de génération d'arbres de dérivation que nous proposons est un algorithme de type Earley intégrant un ensemble de techniques d'optimisation bien connues: tabulation, partage-compression (sharing-packing) et indexation basée sur la sémantique. Dans la seconde partie de la thèse, nous explorons comment notre réalisateur de surface basé sur SemTAG peut être utilisé pour la génération (semi-)automatique d'exercices de grammaire. Habituellement, les enseignants éditent manuellement les exercices et leurs solutions et les classent au regard de leur degré de difficulté ou du niveau attendu de l'apprenant. Un courant de recherche dans le Traitement Automatique des Langues (TAL) pour l'apprentissage des langues assisté par ordinateur traite de la génération (semi-)automatique d'exercices. Principalement, ces travaux s'appuient sur des textes extraits du Web, utilisent des techniques d'apprentissage automatique et des techniques d'analyse de textes (par exemple, analyse de phrases, POS tagging, etc.). Ces approches confrontent l'apprenant à des phrases qui ont des syntaxes potentiellement complexes et du vocabulaire varié. En revanche, l'approche que nous proposons dans cette thèse aborde la génération (semi-)automatique d'exercices du type rencontré dans les manuels pour l'apprentissage des langues. Il s'agit, en d'autres termes, d'exercices dont la syntaxe et le vocabulaire sont faits sur mesure pour des objectifs pédagogiques et des sujets donnés. Les approches de génération basées sur des grammaires associent les phrases du langage naturel avec une représentation linguistique fine de leur propriété morpho-syntaxiques et de leur sémantique grâce à quoi il est possible de définir un langage de contraintes syntaxiques et morpho-syntaxiques permettant la sélection de phrases souches en accord avec un objectif pédagogique donné. Cette représentation permet en outre d'opérer un post-traitement des phrases sélectionées pour construire des exercices de grammaire / In this work, we explore how Natural Language Generation (NLG) techniques can be used to address the task of (semi-)automatically generating language learning material and activities in Camputer-Assisted Language Learning (CALL). In particular, we show how a grammar-based Surface Realiser (SR) can be usefully exploited for the automatic creation of grammar exercises. Our surface realiser uses a wide-coverage reversible grammar namely SemTAG, which is a Feature-Based Tree Adjoining Grammar (FB-TAG) equipped with a unification-based compositional semantics. More precisely, the FB-TAG grammar integrates a flat and underspecified representation of First Order Logic (FOL) formulae. In the first part of the thesis, we study the task of surface realisation from flat semantic formulae and we propose an optimised FB-TAG-based realisation algorithm that supports the generation of longer sentences given a large scale grammar and lexicon. The approach followed to optimise TAG-based surface realisation from flat semantics draws on the fact that an FB-TAG can be translated into a Feature-Based Regular Tree Grammar (FB-RTG) describing its derivation trees. The derivation tree language of TAG constitutes a simpler language than the derived tree language, and thus, generation approaches based on derivation trees have been already proposed. Our approach departs from previous ones in that our FB-RTG encoding accounts for feature structures present in the original FB-TAG having thus important consequences regarding over-generation and preservation of the syntax-semantics interface. The concrete derivation tree generation algorithm that we propose is an Earley-style algorithm integrating a set of well-known optimisation techniques: tabulation, sharing-packing, and semantic-based indexing. In the second part of the thesis, we explore how our SemTAG-based surface realiser can be put to work for the (semi-)automatic generation of grammar exercises. Usually, teachers manually edit exercises and their solutions, and classify them according to the degree of dificulty or expected learner level. A strand of research in (Natural Language Processing (NLP) for CALL addresses the (semi-)automatic generation of exercises. Mostly, this work draws on texts extracted from the Web, use machine learning and text analysis techniques (e.g. parsing, POS tagging, etc.). These approaches expose the learner to sentences that have a potentially complex syntax and diverse vocabulary. In contrast, the approach we propose in this thesis addresses the (semi-)automatic generation of grammar exercises of the type found in grammar textbooks. In other words, it deals with the generation of exercises whose syntax and vocabulary are tailored to specific pedagogical goals and topics. Because the grammar-based generation approach associates natural language sentences with a rich linguistic description, it permits defining a syntactic and morpho-syntactic constraints specification language for the selection of stem sentences in compliance with a given pedagogical goal. Further, it allows for the post processing of the generated stem sentences to build grammar exercise items. We show how Fill-in-the-blank, Shuffle and Reformulation grammar exercises can be automatically produced. The approach has been integrated in the Interactive French Learning Game (I-FLEG) serious game for learning French and has been evaluated both based in the interactions with online players and in collaboration with a language teacher

Le but de cette thèse est d'étudier les trois problèmes suivantes : 1) On s'intéresse à la stabilité des cônes normaux et des sous-différentiels via deux types de convergence d'ensembles et de fonctions : La convergence au sens de Mosco et celle d'Attouch-Wets. Les résultats obtenus peuvent être vus comme une extension du théorème d'Attouch aux fonctions non nécessairement convexes sur des espaces de Banach localement uniformément convexes. 2) Pour une bornologie β donnée sur un espace de Banach X, on étudie la validité de la formule suivante (…). Ici Tβ(C; x) et Tc(C; x) désignent le β -cône tangent et le cône tangent de Clarke à C en x. On montre que si, X x X est ∂β-« trusted » alors cette formule est valable pour tout ensemble fermé non vide C ⊂ X et x ∈ C. Cette classe d'espaces contient les espaces ayant une norme équivalent β-différentiable, etplus généralement les espaces possédant une fonction "bosse" lipschitzienne et β-différentiable). Comme conséquence, on obtient que pour la bornologie de Fréchet, cette formule caractérise les espaces d'Asplund. 3) On examine la convexité des ensembles de Chebyshev. Il est bien connu que, dans un espace normé réflexif ayant la propriété Kadec-Klee, tout ensemble de Chebyshev faiblement fermé est convexe. On démontre que la condition de faible fermeture peut être remplacée par la fermeture faible locale, c'est-à-dire pour tout x ∈ C il existe ∈ > 0 tel que C ∩ B(x, ε) est faiblement fermé. On montre aussi que la propriété Kadec-Klee n'est plus exigée lorsque l'ensemble de Chebyshev est représenté comme une union d'ensembles convexes fermés. / The aim of this thesis is to study the following three problems: 1) We are concerned with the behavior of normal cones and subdifferentials with respect to two types of convergence of sets and functions: Mosco and Attouch-Wets convergences. Our analysis is devoted to proximal, Fréchet, and Mordukhovich limiting normal cones and subdifferentials. The results obtained can be seen as extensions of Attouch theorem to the context of non-convex functions on locally uniformly convex Banach space. 2) For a given bornology β on a Banach space X we are interested in the validity of the following "lim inf" formula (…).Here Tβ(C; x) and Tc(C; x) denote the β-tangent cone and the Clarke tangent cone to C at x. We proved that it holds true for every closed set C ⊂ X and any x ∈ C, provided that the space X x X is ∂β-trusted. The trustworthiness includes spaces with an equivalent β-differentiable norm or more generally with a Lipschitz β-differentiable bump function. As a consequence, we show that for the Fréchet bornology, this "lim inf" formula characterizes in fact the Asplund property of X. 3) We investigate the convexity of Chebyshev sets. It is well known that in a smooth reflexive Banach space with the Kadec-Klee property every weakly closed Chebyshev subset is convex. We prove that the condition of the weak closedness can be replaced by the local weak closedness, that is, for any x ∈ C there is ∈ > 0 such that C ∩ B(x, ε) is weakly closed. We also prove that the Kadec-Klee property is not required when the Chebyshev set is represented by a finite union of closed convex sets.