In formal language theory, studying shortest strings in languages, and variations thereof, can be useful since these strings can serve as small witnesses for properties of the languages, and can also provide bounds for other problems involving languages. For example, the length of the shortest string accepted by a regular language provides a lower bound on the state complexity of the language. In Chapter 1, we introduce some relevant concepts and notation used in automata and language theory, and we show some basic results concerning the connection between the length of the shortest string and the nondeterministic state complexity of a regular language. Chapter 2 examines the effect of the intersection operation on the length of the shortest string in regular languages. A tight worst-case bound is given for the length of the shortest string in the intersection of two regular languages, and loose bounds are given for two variations on the problem. Chapter 3 discusses languages that are defined over a free group instead of a free monoid. We study the length of the shortest string in a regular language that becomes the empty string in the free group, and a variety of bounds are given for different cases. Chapter 4 mentions open problems and some interesting observations that were made while studying two of the problems: finding good bounds on the length of the shortest squarefree string accepted by a deterministic finite automaton, and finding an efficient way to check if a finite set of finite words generates the free monoid. Some of the results in this thesis have appeared in work that the author has participated in \cite{AngPigRamSha,AngShallit}.

In hyperscale data center operations, automation is applied in many ways as it is becomes very hard to scale otherwise. There are however areas relating to understanding, grouping and diagnosing of error reports that are done manually at Facebook today. This master's thesis investigates solutions for applying unsupervised clustering methods to server error reports, server properties and historical data to speed up and enhance the process of finding and root causing systematic issues. By utilizing data representations that can embed both key-value data and historical event log data, the thesis shows that clustering algorithms together with data representations that capture syntactic and semantic structures in the data can be applied with good results in a real-world scenario.

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.

L'apprentissage de langages réguliers est un sous-ensemble de l'apprentissage automatique qui s'est révélé utile dans de nombreux domaines tels que l'intelli-gence artificielle, les réseaux de neurones, l'exploration de données, la vérification, etc. De plus, l'intérêt dans les langages définis sur des alphabets infinis ou de grande taille est croissant au fil des années. Même si plusierurs propriétés et théories se généralisent à partir du cas fini, l'apprentissage de tels langages est une tâche difficile.En effet, dans ce contexte, l'application naïve des algorithmes d'apprentissage traditionnel n'est pas possible.Dans cette thèse, nous présentons un schéma algorithmique général pour l'ap-prentissage de langages définis sur des alphabets infinis ou de grande taille, comme par exemple des sous-ensembles bornés de N or R ou des vecteurs booléens de grandes dimensions. Nous nous restreignons aux classes de langages qui sont acceptés par des automates déterministes symboliques utilisant des prédicats pour définir les transitions, construisant ainsi une partition finie de l'alphabet pour chaque état.Notre algorithme d'apprentissage, qui est une adaptation du L* d'Angluin, combine l'apprentissage classique d'un automate par la caractérisation de ses états, avec l'apprentissage de prédicats statiques définissant les partitions de l'alphabet. Nous utilisons l'apprentissage incrémental avec la propriété que deux types de requêtes fournissent une information suffisante sur le langage cible. Les requêtes du premier type sont les requêtes d'adhésions, qui permettent de savoir si un mot proposé appartient ou non au langage cible. Les requêtes du second type sont les requêtes d'équivalence, qui vérifient si un automate proposé accepte le langage cible; dans le cas contraire, un contre-exemple est renvoyé.Nous étudions l'apprentissage de langages définis sur des alphabets infinis ou de grande tailles dans un cadre théorique et général, mais notre objectif est de proposer des solutions concrètes pour un certain nombre de cas particuliers. Ensuite, nous nous intéressons aux deux principaux aspects du problème. Dans un premier temps, nous supposerons que les requêtes d'équivalence renvoient toujours un contre-exemple minimal pour un ordre de longueur-lexicographique quand l'automate proposé est incorrect. Puis dans un second temps, nous relâchons cette hypothèse forte d'un oracle d'équivalence, et nous la remplaçons avec une hypothèse plus réaliste où l'équivalence est approchée par un test sur les requêtes qui utilisent un échantillonnage sur l'ensemble des mots. Dans ce dernier cas, ce type de requêtes ne garantit pas l'obtention de contre-exemples, et par conséquent de contre-exemples minimaux. Nous obtenons alors une notion plus faible d'apprent-issage PAC (Probably Approximately Correct), permettant l'apprentissage d'une approximation du langage cible.Tout les algorithmes ont été implémentés, et leurs performances, en terme de construction d'automate et de taille d'alphabet, ont été évaluées empiriquement. / Learning regular languages is a branch of machine learning, which has been proved useful in many areas, including artificial intelligence, neural networks, data mining, verification, etc. On the other hand, interest in languages defined over large and infinite alphabets has increased in recent years. Although many theories and properties generalize well from the finite case, learning such languages is not an easy task. As the existing methods for learning regular languages depends on the size of the alphabet, a straightforward generalization in this context is not possible.In this thesis, we present a generic algorithmic scheme that can be used for learning languages defined over large or infinite alphabets, such as bounded subsets of N or R or Boolean vectors of high dimensions. We restrict ourselves to the class of languages accepted by deterministic symbolic automata that use predicates to label transitions, forming a finite partition of the alphabet for every state.Our learning algorithm, an adaptation of Angluin's L*, combines standard automaton learning by state characterization, with the learning of the static predicates that define the alphabet partitions. We use the online learning scheme, where two types of queries provide the necessary information about the target language. The first type, membership queries, answer whether a given word belongs or not to the target. The second, equivalence queries, check whether a conjectured automaton accepts the target language, a counter-example is provided otherwise.We study language learning over large or infinite alphabets within a general framework but our aim is to provide solutions for particular concrete instances. For this, we focus on the two main aspects of the problem. Initially, we assume that equivalence queries always provide a counter-example which is minimal in the length-lexicographic order when the conjecture automaton is incorrect. Then, we drop this ``strong'' equivalence oracle and replace it by a more realistic assumption, where equivalence is approximated by testing queries, which use sampling on the set of words. Such queries are not guaranteed to find counter-examples and certainly not minimal ones. In this case, we obtain the weaker notion of PAC (probably approximately correct) learnability and learn an approximation of the target language. All proposed algorithms have been implemented and their performance, as a function of automaton and alphabet size, has been empirically evaluated.

Ever since Bengt Sigurd laid out the first comprehensive description of Swedish phonotactics in 1965, it has been the main point of reference within the field. This thesis attempts a new approach, by presenting a computational and statistical model of Swedish phonotactics, which can be built by any corpus of IPA phonetic script. The model is a weighted trie, represented as a finite state automaton, where states are phonemes linked by transitions in valid phoneme sequences, which adds the benefits of being probabilistic and expressible by regular languages. It was implemented using the Nordisk Språkteknologi (NST) pronunciation lexicon and was used to test against a couple of rulesets defined in Sigurd relating to initial two consonant clusters of phonemes and phoneme classes. The results largely agree with Sigurd's rules and illustrated the benefits of the model, in that it effectively can be used to pattern match against phonotactic information using regular expression-like syntax. / Ända sedan Bengt Sigurd lade fram den första övergripande beskrivningen av svensk fonotax 1965, så har den varit den främsta referenspunkten inom fältet. Detta examensarbete försöker sig på en ny infallsvinkel genom att presentera en beräkningsbar och statistisk modell av svensk fonotax som kan byggas med en korpus av fonetisk skrift i IPA. Modellen är en viktad trie, representerad som en ändlig automat, vilket har fördelarna av att vara probabilistisk och kunna beskrivas av reguljära språk. Den implementerades med hjälp av uttalslexikonet från Nordisk Språkteknologi (NST) och användes för att testa ett par regelgrupper av initiala två-konsonant kluster av fonem och fonemklasser definierad av Sigurd. Resultaten stämmer till större del överens med Sigurds regler och visar på fördelarna hos modellen, i att den effektivt kan användas för att matcha mönster av fonotaktisk information med hjälp av en liknande syntax för reguljära uttryck.

The Regular Expression (RegEx) is one of the most important computer science technologies used for searching through text. Used commonly in almost every corner of computer science that is dependent on searching, it is imperative that they are made to be efficient. Usually, RegEx are implemented through the use of a process called interpretation. This thesis explores the possibility and execution time benefits of compiling the RegEx as part of the program instead of interpreting it. For this purpose, a prototype implementation was developed in the Rust programming language. Using this prototype, execution time benchmarks were performed that compare the optimised, and commonly used, interpreted variant against the thesis’ unoptimised compiled version. While the results did not determine a clear preferred method in terms of execution time, they did highlight the potential that exists in compiling RegEx. With some of the tests showing faster execution times in the prototype, there are strong arguments for future research into this field, where the compilation of RegEx can come to benefit from the optimisations present in the interpreted norm. / Regulära uttryck (EN: Regular Expression; RegEx) är en av de mest använda datalogiteknikerna för att söka igenom text. Eftersom det är använt inom många delar av datalogi så är teknikens effektivitet viktig. I norm är RegEx genomförda med en process kallad tolkning. Denna uppsats utforskar möjligheten och tidsförmåner att kompilera dessa RegEx som en del av det utomliggande programmet istället för att tolka det. För det syftet skapades en prototyp i programmeringsspråket Rust. Denna prototyp användes då för att utföra tidstest där den optimerade tolkade normen jämnfördes med avhandlingens kompilerade icke optimerade variant. De producerade resultaten visade ingen föredragen metod men betonade möjligheterna med att kompilera RegEx. Eftersom vissa av testerna visade snabbare utförande med prototypen finns det starka argument för ytterligare forskning inom detta område. På så sätt kan den kompilerade formen ta del av den utveckling som den tolkade normen redan har.

<p>Jezik nad E je proizvoljan skup reci nad E, tj. proizvoljan podskup slobodnog monoida E*. Jezici nad datom azbukom formiraju al&shy; gebre jezika, sa operacijama unije, konkatenacije (dopisivanja red), Kleene-jeve iteracije i sa 0, {A} kao konstantama. Regularni jezici nad E su elementi podalgebre algebre jezika nad E generisane konačnim jezicima. Ispostavlja se da algebre jezika generi&scaron;u isti varijetet (i stoga zadovoljavaju iste iden&shy;titete) kao i algebre binarnih relacija snabdevene operacijama unije, kompozi&shy;cije, refleksivno-tranzitivnog zatvorenja i praznom relacijom i dijagonalom kao konstantama. Reč je o varijetetu Kleenejevih algebri, i slobodne algebre tog varijeteta su ba&scaron; algebre regularnih jezika. Na početku disertacije, izloženi su neki aspekti algebarske teorije automata i formalnih jezika, teorije binarnih relacija i univerzalne algebre, relevantni za ispitivanje identiteta na algebrama jezika. Zatim je dat klasični rezultat (Redko, 1964.) da varijetet Kleenejevih algebri nema konačnu bazu identiteta. Ovde je prikazan dokaz Conwaya iz 1971., budući da on sadrži neke ideje koje su se pokazale korisne za dalji rad. Glave 3 i 4 sadrže originalne rezultate usmerene na profinjenje Redkovog rezultata. Pokazano je da uzroci beskonačnosti baze identiteta za Kleenejeve algebre leže u interakciji operacija konkatenacije i iteracije jezika (odnosno, kompozicije i refleksivno-tranzitivnog zatvorenja relacija). Drugim recima, klasa redukata algebri jezika bez operacije unije nema konačnu bazu identiteta. To daje odgovor na problem D. A. Bredikhina iz 1993. godine. S druge strane, pro&scaron;irenjem tipa Kleenejevih algebri involutivnom operacijom inverza jezika, odnosno relacija, takođe se dolazi do beskonačno baziranih varijeteta, čime se re&scaron;ava problem B. Jonssona iz 1988. godine. Analogno, komutativni jezici nad E su proizvoljni podskupovi slobodnog komutativnog monoida E&reg;. U Glavi 5 je dokazano da se jednakosna teorija algebri komutativnih jezika poklapa sa jednakosnom teorijom algebre (regu&shy;larnih) jezika nad jednoelementnim alfabetom, &scaron;to daje odgovor na problem koji je jo&scaron; 1969. formulisao A. Salomaa u svojoj monografiji&nbsp; Theory of Au&shy;tomata.Na taj način, iz poznatih rezultata o jednakosnoj aksiomatizaciji komutativnih jezika se dobija jedna baza za algebre jezika nad jednoelement&shy;nim alfabetom, kao i veoma kratak dokaz poznate činjenice (takođe Redko, 1964.) da algebre komutativnih jezika nemaju konačnu bazu identiteta. Na kraju disertacije, identiteti Kleenejevih algebri se posmatraju u kon&shy;tekstu dinamičkih algebri. Reč je o algebarskoj verziji dinamičkih logika, koje su konstruisane sedamdesetih godina kao matematički model rada računara, kada se na njima izvr&scaron;ava program pisan u nekom imperativnom program&shy; skom jeziku. Na primer, problemi verifikacije i ekvivalentnosti programa se lako izražavaju preko identiteta dinamičkih algebri, tako da razne njihove jednakosne osobine odgovaraju pojmovima iz teorijskog računarstva. Takođe, interesatno je da je jednakosna teorija Kleenejevih algebri &rsquo;&rsquo; kodirana&rdquo; u konačno baziranoj jednakosnoj teoriji dinamičih algebri. Polazeći od poznatih rezul&shy;tata za dvosortne dinamičke algebre (pri čemu je jedna komponenta algebra istog tipa kao i Kleenejeve algebre, dok je druga Booleova algebra), neki od tih rezultata su transformisani i pro&scaron;ireni za Jonssonove dinamičke algebre (jednosortne modele dinamičkih logika). Na primer, ako se Kleenejeva algebra K može predstaviti kao konačan direktan proizvod slobodnih algebri varijeteta Kleenejevih algebri generisanih Kleenejevim relacionim algebrama, tada vari&shy;jetet K-dinamičkih algebri ima odlučivu jednakosnu teoriju. Odavde se izvodi da svaki varijetet Kleenejevih algebri generisan Kleenejevim relacionim algeb&shy;rama takođe ima odlučivu jednakosnu teoriju.</p> / <p>A language over &pound; is an arbitrary set of words, i.e. any subset of the free monoid &pound;*. All languages over a given alphabet form the algebra of languages, which is equipped with the operations of union, concate&shy;nation, Kleene iteration and 0, {A } as constants. Regular languages over &pound; are the elements of the subalgebra of the algebra of languages over &pound; generated by finite languages. It turns out that algebras of languages generate exactly the same variety as algebras of binary relations, endowed with union, rela&shy;tion composition, formation of the refelxive-transitive closure and the empty relation and the diagonal as constants. The variety in question is the vari&shy;ety of Kleene algebras, and the algebras of regular languages are just its free algebras. The present dissertation starts with several aspects of algebraic theory of automata and formal languages, theory of binary relations and universal alge&shy;bra, which are related to problems concerning identities of language algebras. This material is followed by the classical result (Redko, 1964) claiming that the variety of Kleene algebras have no finite equational base. We present the proof of Conway from 1971, since it contains some ideas which can be used for generalizations in different directions. Chapters 3 and 4 contain original results which refine the one of Redko. It is shown that the cause of nonfinite axiomatizability of Kleene algebras lies in the superposition of the concatenation and the iteration of languages, that is, composition of relations and reflexive-transitive closure. In other words, the class of -(--free reducts of algebras of languages has no finite equational base, which answers in the negative a problem of D. A. Bredikhin from 1993. On the other hand, by extending the type of Kleene algebras by the involutive operation of inverse of&nbsp; languages (converse of relations), we also obtain a nonfinitely based variety, which solves a problem of B. Jonsson from 1988. Analogously, commutative languages over E are defined as subsets of the free commutative monoid &pound;&reg;. It is proved in Chapter 5 that equational the&shy; ories of algebras of commutative languages and, respectively, of the algebra of (regular) languages over the one-element alphabet, coincide. This result settles a thirty year old problem of A. Salomaa, formulated back in his wellknown monograph&nbsp; Theory of Automata.Thus, we obtain an equational base for the algebra of one-letter languages, and, on the other hand, a very short proof of another Redko&rsquo;s result from 1964, according to which there is no finite equational base for algebras of commutative languages. Finally, identities of Kleene algebras are considered in the context of dy&shy;namic algebras, which are just algebraic counterparts of dynamic logics. They were discovered in the seventies as a result of the quest for an appropriate logic for reasoning about computer programs written in an imperative pro&shy; gramming language. For example, problems concerning program verification and equivalence can be easily translated into identities of dynamic algebras, so that many of their equational properties correspond to notions from computer science. It is also interesting that the whole equational theory of Kleene alge&shy; bras is &rsquo;&rsquo;encoded&rdquo; in the finitely based equational theory of dynamic algebras.<br />Starting with known results on two-sorted dynamic algebras (where one com&shy; ponent is an algebra of the same signature as Kleene algebras, while the other is a Boolean algebra), some of those results are transformed and extended for Jonsson dynamic algebras (that is, one-sorted models of dynamic logics). For example, if a Kleene algebra K can be represented as a finite direct product of free algebras of varieties of Kleene algebras generated by Kleene relation algebras, then the variety of K-dynamic algebras has a decidable equational theory. The latter yields that all varieties of Kleene algebras generated by Kleene relation algebras have decidable equational theories, too.</p>

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.

Le problème de séparation pour une classe de langages S est le suivant : étant donnés deux langages L1 et L2, existe-t-il un langage appartenant à S qui contient L1, en étant disjoint de L2 ? Si les langages à séparer sont des langages réguliers, le problème de séparation pour la classe S est plus général que le problème de l'appartenance à cette classe, et nous fournit des informations plus détaillées sur la classe. Ce problème de séparation apparaît dans un contexte algébrique sous la forme des parties ponctuelles, et dans un contexte profini sous la forme d'un problème de séparation topologique. Pour quelques classes de langages spécifiques, ce problème a été étudié en utilisant des méthodes profondes de la théorie des semigroupes profinis.Dans cette thèse, on s'intéresse, dans un premier temps, à la décidabilité de ce problème pour plusieurs sous-classes des langages réguliers. Dans un second temps, on s'intéresse à obtenir un langage séparateur, s'il existe, ainsi qu'à la complexité de ces problèmes.Nous établissons une approche générique pour prouver que le problème de séparation est décidable pour une classe de langages donnée. En utilisant cette approche, nous obtenons la décidabilité du problème de séparation pour les langages testables par morceaux, les langages non-ambigus, les langages localement testables, et les langages localement testables à seuil. Ces classes correspondent à des fragments de la logique du premier ordre, et sont parmi lesclasses de langages réguliers les plus étudiées. De plus, cette approche donne une description d'un langage séparateur, pourvu qu'il existe. / The separation problem, for a class S of languages, is the following: given two input languages, does there exist a language in S that contains the first language and that is disjoint from the second langage ?For regular input languages, the separation problem for a class S subsumes the classical membership problem for this class, and provides more detailed information about the class. This separation problem first emerged in an algebraic context in the form of pointlike sets, and in a profinite context as a topological separation problem. These problems have been studied for specific classes of languages, using involved techniques from the theory of profinite semigroups.In this thesis, we are not only interested in showing the decidability of the separation problem for several subclasses of the regular languages, but also in constructing a separating language, if it exists, and in the complexity of these problems.We provide a generic approach, based on combinatorial arguments, to proving the decidability of this problem for a given class. Using this approach, we prove that the separation problem is decidable for the classes of piecewise testable languages, unambiguous languages, and locally (threshold) testable languages. These classes are defined by different fragments of first-order logic, and are among the most studied classes of regular languages. Furthermore, our approach yields a description of a separating language, in case it exists.

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.