Les expressions rationnelles et les automates finis sont des objets mathématiques permettant de représenter les langages rationnels. Le lien entre ces structures est le sujet de nombreux thèmes de recherche. Chacun de ces modèles présentent avantages et inconvénients. Nous nous proposons d'établir de nouveaux opérateurs, les multi-tildes-barres, permettant de créer un modèle d'expression se situant entre la structure d'automate et celle d'expression rationnelle simple, utilisant l'union, la concaténation, et l'étoile de Kleene. Les multi-tildes-barres sont basées sur des opérations relativement simples sur les langages, l'ajout et l'élimination du mot vide. Nous étendons les méthodes de conversion classiques entre expressions rationnelles simples et automates finis aux expressions utilisant ces nouveaux opérateurs. Nous montrons également que le pouvoir de factorisation de ces nouvelles expressions est exponentiellement plus grand que celui des expressions rationnelles simples.

L'ouvrage unifie les paradigmes du darwinisme universel, de la psycholinguistique développementale et de la linguistique computationnelle afin de fournir un récit nouveau d'ontogénie de structures linguistiques chez les agents humains ou bien artificiels. La thèse est précédée d'un volume supplémentaire intitulé «Fondements conceptuels» qui présente une théorie de l'évolution intra-mentale qui pose l'hypothèse que l'ontogénie d'un esprit individuel peut être interprétée et même simulée comme un processus impliquant la réplication, la variation et la sélection des structures qui encodent de l'information. La dissertation elle-même présente quatre simulations distinctes abordant quatre problèmes distincts. La 0ème simulation illustre comment l'optimisation évolutionnist pourrait conduire à la découverte d'idées utiles concernant l'énigme cryptologique connue sous le nom de Voynich Manuscript. La première simulation montre comment la théorie des prototypes, les architectures symboliques vectorielles et l'optimisation évolutionniste peuvent être mutuellement combinées afin de produire une nouvelle méthode d'apprentissage automatique supervisée. La deuxième simulation utilise une approche similaire pour démontrer que l'optimisation évolutive peut découvrir des constellations minimalistes et légères de marqueurs de partie de discours. La dernière simulation vise le «saint graal» de la linguistique computationnelle, c'est-à-dire le problème de «l'induction grammaticale» et montre que le problème peut être potentiellement résolu en utilisant une stratégie évolutive capable de combler l'écart entre le domaine subsymbolique et le domaine symbolique. / Our thesis unifes paradigms of universal darwinism, developmental psycholinguistics and computational linguistics in order to furnish a novel account of language development in human as well as artificial language-acquiring agents. Thesis is preceded by a supplementary volume called "Conceptual Foundations" which presents a so-called "Theory of Intramental Evolution" which postulates that ontogeny of an individual mind can be interpreted and even simulated as a process involving replication, variation and selection of information-encoding cognitive structures. The dissertation itself presents four distinct simulations addressing four distinct problems. Zeroth simulation illustrates how evolutionary optimization could lead to discovery of useful insights concerning the cryptological riddle known as Voynich Manuscript. The first simulation shows how theory of prototypes, vector symbolic architectures and evolutionary optimization can be mutually combined in order to yield a novel supervised machine-learning method. Second simulation uses a similiar approach in order to indicate that evolutionary optimization can discover minimalist and lightweight constellations of part-of-speech taggers. The last simulation targets the "holy grail" of computational linguistics, i.e. the problem of "grammar induction" and shows that the problem can be potentially solved by using an evolutionary strategy able to bridge the gap between subsymbolic realm of vector spaces and symbolic realm of grammar-representing regular expressions.

Les systèmes dynamiques présentent des comportements temporels qui peuvent être exprimés sous diverses formes séquentielles telles que des signaux, des ondes, des séries chronologiques et des suites d'événements. Détecter des motifs sur de tels comportements temporels est une tâche fondamentale pour comprendre et évaluer ces systèmes. Étant donné que de nombreux comportements du système impliquent certaines caractéristiques temporelles, le besoin de spécifier et de détecter des motifs de comportements qui implique des exigences de synchronisation, appelées motifs temporisés, est évidente.Cependant, il s'agit d'une tâche non triviale due à un certain nombre de raisons, notamment la concomitance des sous-systèmes et la densité de temps.La contribution principale de cette thèse est l'introduction et le développement du filtrage par motif temporisé, c'est-à-dire l'identification des segments d'un comportement donné qui satisfont un motif temporisé. Nous proposons des expressions rationnelles temporisées (TRE) et la logique de la boussole métrique (MCL) comme langages de spécification pour motifs temporisés. Nous développons d'abord un nouveau cadre qui abstraite le calcul des aspects liés au temps appelé l'algèbre des relations temporisées. Ensuite, nous fournissons des algorithmes du filtrage hors ligne pour TRE et MCL sur des comportements à temps dense à valeurs discrètes en utilisant ce cadre et étudions quelques extensions pratiques.Il est nécessaire pour certains domaines d'application tels que le contrôle réactif que le filtrage par motif doit être effectué pendant l'exécution réelle du système. Pour cela, nous fournissons un algorithme du filtrage en ligne pour TREs basé sur la technique classique des dérivées d'expressions rationnelles. Nous croyons que la technique sous-jacente qui combine les dérivées et les relations temporisées constitue une autre contribution conceptuelle majeure pour la recherche sur les systèmes temporisés.Nous présentons un logiciel libre Montre qui implémente nos idées et algorithmes. Nous explorons diverses applications du filtrage par motif temporisé par l'intermédiaire de plusieurs études de cas. Enfin, nous discutons des orientations futures et plusieurs questions ouvertes qui ont émergé à la suite de cette thèse. / Dynamical systems exhibit temporal behaviors that can be expressed in various sequential forms such as signals, waveforms, time series, and event sequences. Detecting patterns over such temporal behaviors is a fundamental task for understanding and assessing these systems. Since many system behaviors involve certain timing characteristics, the need to specify and detect patterns of behaviors that involves timing requirements, called timed patterns, is evident. However, this is a non-trivial task due to a number of reasons including the concurrency of subsystems and density of time.The key contribution of this thesis is in introducing and developing emph{timed pattern matching}, that is, the act of identifying segments of a given behavior that satisfy a timed pattern. We propose timed regular expressions (TREs) and metric compass logic (MCL) as timed pattern specification languages. We first develop a novel framework that abstracts the computation of time-related aspects called the algebra of timed relations. Then we provide offline matching algorithms for TRE and MCL over discrete-valued dense-time behaviors using this framework and study some practical extensions.It is necessary for some application areas such as reactive control that pattern matching needs to be performed during the actual execution of the system. For that, we provide an online matching algorithm for TREs based on the classical technique of derivatives of regular expressions. We believe the underlying technique that combines derivatives and timed relations constitutes another major conceptual contribution for timed systems research.Furthermore, we present an open-source tool Montre that implements our ideas and algorithms. We explore diverse applications of timed pattern matching over several case studies using Montre. Finally we discuss future directions and several open questions emerged as a result of this thesis.

Cette thèse a pour but d’étudier des propriétés structurelles d’automates étendant celle du déterminisme, et les langages pouvant être dénotés par une expression rationnelle dont l’automate des positions présente l’une de ces propriétés. Si Book et al. ont montré que tous les langages rationnels peuvent être reconnus par un automate des positions non-ambigu, Brüggemann-Klein et Wood ont montré que ceux pouvant l’être par un automate des positions déterministe forment une famille strictement incluse dans celle des rationnels. Nous nous intéressons aux extensions de cette famille, en cherchant à caractériser leurs langages, et à étudier leur hiérarchie interne et leur inclusion entre elles. / This thesis aims to study structural properties of automata extending determinism, and the languages that can be denoted by a regular expression of which the position automaton has one such property. If Book et al. showed that all regular languages can be recognized by an unambiguous position automaton, Brüggemann-Klein and Wood showed that only a proper subset of them can be recognized by a deterministic position automaton. We focus on extensions of this subfamily, by seeking to characterize their languages, and to study their internal hierarchy and how they relate to each other.