Dissertations / Theses on the topic 'Automate mathématique'

Ce travail de thèse traite de la modélisation et du contrôle des maladies infectieuses à l’aide des automates cellulaires. Nous nous sommes d’abord focalisés sur l’étude d’un modèle de type SEIR. Nous avons pu monter d’une part qu’un voisinage fixe pouvait entrainer une sous-évaluation de l’incidence et de la prévalence et d’autre part que sa structure a un impact direct sur la structure de la distribution de la maladie. Nous nous sommes intéressés également la propagation des maladies vectorielles à travers un modèle de type SIRS-SI multi-hôtes dans un environnement hétérogène.Les hôtes y étaient caractérisés par leur niveau de compétence et l’environnement par la variation du taux de reproduction et de mortalité. Son application à la maladie de Chagas, nous a permis de montrer que l’hétérogénéité de l’habitat et la diversité des hôtes contribuaient à faire baisser l’infection. Cependant l’un des principaux résultats de notre travail à été la formulation du nombre de reproduction spatiale grâce à deux matrices qui représentent les coefficients d’interactions entre les différentes cellules du réseau
This PhD thesis considers the general problem of epidemiological modelling and control using cellular automata approach.We first focused on the study of the SEIR model. On the one hand, we have shown that the traditionnal neighborhood contribute to underestimate the incidence and prevalence of infection disease. On the other hand, it appeared that the spatial distribution of the cells in the lattice have a real impact on the disease spreading. The second study concerns the transmission of the vector-borne disease in heterogeneous landscape with host community. We considered a SIRS-SI with various level of competence at witch the environnment heterogeneity has been characterized by the variation of the birth flow and the death rate. We simulated the Chagas disease spreading and shown that the heterogeneity of habitat and host diversity contribute to decrease the infection. One of the most important results of our work, was the proposition of the spatial reproduction number expression based on two matrices that represent the interaction factors between the cells in the lattice

Nous donnons une nouvelle preuve de la rationalité de la fonction zéta d'un système sofique, qui fournit un algorithme permettant de calculer cette fonction. Enfin, nous proposons une optimisation de cet algorithme

Les problèmes traités et les résultats obtenus dans ce travail s'inscrivent essentiellement dans le domaine de la théorie des automates, la logique mathématique et leurs applications. Dans un premier temps on utilise les automates finis pour démontrer l'automaticité de plusieurs structures logiques sur des mots finis écrits dans un alphabet infini dénombrable. Ceci nous permet de déduire la décidabilité des théories logiques associées à ces structures. On a considéré par exemple la structure $X=(Sigma^*;prec,clone)$ où $Sigma^*$ désigne l'ensemble des mots finis sur l'alphabet infini dénombrable $Sigma$, $prec$ désigne la relation de préfixe et $clone$ désigne le prédicat qui est vrai pour un mot se terminant par deux lettres identiques. On a démontré l'automaticité de la structure $X$ et la décidabilité de sa théorie du premier ordre et de sa théorie monadique du second ordre. On a aussi considéré des extensions de la structure $X$ obtenues en ajoutant des prédicats comme $sim$ qui est vrai pour deux mots de même longueur. Nous avons en particulier démontré la $M$-automaticité de la structure $(Sigma^*;prec,clone,sim)$, d'où la décidabilité de sa théorie du premier ordre. On a par ailleurs étudié des structures qui comportent le prédicat $diff$ qui est vrai pour un mot dont les lettres sont toutes distinctes. En particulier on a démontré l'automaticité de la structure $D=(Sigma^*;prec,clone,diff)$ et la décidabilité de sa théorie du premier ordre et de sa théorie monadique du second ordre. On a également obtenu, par interprétation logique, des résultats de décidabilité et des résultats d'indécidabilité pour plusieurs variantes des structures $X$ et $D$, ainsi que pour des familles de structures appelées emph{structure d'applications exclusives} et emph{structure de décomposition}.Dans un deuxième temps on s'est intéressé au problème de la réduction du nombre de transitions dans les automates finis. On a commencé par étendre le concept de emph{Common Follow Sets} d'une expression régulière aux automates finis homogènes. On a montré comment établir une liaison assez directe entre des systèmes de CFS spécifiques et les arbres binaires complets. Ce lien est prouvé en utilisant un objet combinatoire appelé emph{triangle d'Ératosthène - Pascal}. Cette correspondance permet de transformer la valeur qui nous intéresse (le nombre de transitions) en une valeur assez naturelle associée aux arbres (le poids d'un arbre). En effet, construire un automate ayant un minimum de transitions revient à trouver un arbre de poids minimal. On a montré, d'une part, que ce nombre de transitions est asymptotiquement équivalent à $n(log_2 n)^2$ (la borne inférieure). D'autre part, les tests expérimentaux montrent que pour les petites valeurs de $n$, les automates minimaux en nombre de transitions coïncident (en nombre et en taille) avec ceux obtenus par notre construction. Cela nous mène à suggérer que notre réduction est finalement une minimisation pour les automates triangulaires. Dans un dernier temps on a présenté une étude expérimentale concernant l'application des automates à trous dans le domaine de la recherche approchée de motif dans les dictionnaires de mots. Contrairement aux complexités théoriques, temps de recherche et espace de stockage exponentiels, nos expérimentations montrent la linéarité de l'automate à trous
This work deals mainly with automata theory, mathematical logic and their applications. In the first part, we use finite automata to prove the automaticity of several logical structures over finite words written in a countable infinite alphabet. These structures involve predicates like $pred$, $clone$ and $diff$, where $x pred y$ holds if $x$ is a strict prefix of $y$, $clone(x)$ holds when the two last letters of $x$ are equal, and $diff(x)$ holds when all letters of $x$ are pairwise distinct. The automaticity results allow to deduce the decidability of logical theories associated with these structures. Other related decidability/undecidability results are obtained by logical interpretation. In the second part, we generalize the concept of Common Follow Sets of a regular expression to homogeneous finite automata. Based on this concept and a particular class of binary trees, we devise an efficient algorithm to reduce/minimize the number of transitions of triangular automata. On the one hand, we prove that the produced reduced automaton is asymptotically minimal, in the sense that for an automaton with $n$ states, the number of transitions in the reduced automaton is equivalent to $n(log_2 n)^2$ , which corresponds at the same time to the upper and the lower known bounds. On the other hand, experiments reveal that for small values of $n$, all minimal automata are exactly those obtained by our reduction, which lead us to conjecture that our construction is not only a reduction but a minimization. In the last part, we present an experimental study on the use of special automata on partial words for the approximate pattern matching problem in dictionaries. Despite exponential theoretical time and space upper bounds, our experiments show that, in many practical cases, these automata have a linear size and allow a linear search time

Le modèle des automates cellulaires constitue un des modèles le mieux établi de physique discrète sur espace euclidien. Ils implantent trois symétries fondamentales de la physique: la causalité, l'homogénéité et la densité finie de l'information. Bien que l'origine des automates cellulaires provienne de la physique, leur utilisation est très répandue comme modèles de calcul distribué dans l'espace (machines auto-réplicantes, problèmes de synchronisation,...), ou bien comme modèles de systèmes multi-agents (congestion du trafic routier, études démographiques,...). Bien qu'ils soient parmi les modèles de calcul distribué les plus étudiés, la rigidité de leur structure interdit toute extension triviale vers un modèle de topologie variant dans le temps, qui se trouve être un prérequis fondamental à la modélisation de certains phénomènes biologiques, sociaux ou physiques, comme par exemple la discrétisation de la relativité générale. Les dynamiques causales de graphes généralisent les automates cellulaires aux graphes arbitraires de degré borné et pouvant varier dans le temps. Dans cette thèse, nous nous attacherons à généraliser certains des résultats fondamentaux de la théorie des automates cellulaires. En munissant nos graphes d'une métrique compacte, nous présenterons deux approches différentes du modèle. Une première approche axiomatique basée sur les notions de continuité et d'invariance par translation, et une deuxième approche constructive, où une règle locale est appliquée en parallèle et de manière synchrone sur l'ensemble des sommets du graphe
Cellular Automata constitute one of the most established model of discrete physical transformations that accounts for euclidean space. They implement three fundamental symmetries of physics: causality, homogeneity and finite density of information. Even though their origins lies in physics, they are widely used to model spatially distributed computation (self-replicating machines, synchronization problems,...), as well as a great variety of multi-agents phenomena (traffic jams, demographics,...). While being one of the most studied model of distributed computation, their rigidity forbids any trivial extension toward time-varying topology, which is a fundamental requirement when it comes to modelling phenomena in biology, sociology or physics: for instance when looking for a discrete formulation of general relativity. Causal graph dynamics generalize cellular automata to arbitrary, bounded degree, time-varying graphs. In this work, we generalize the fundamental structure results of cellular automata for this type of transformations. We endow our graphs with a compact metric space structure, and follow two approaches. An axiomatic approach based on the notions of continuity and shift-invariance, and a constructive approach, where a local rule is applied synchronously on every vertex of the graph. Compactness allows us to show the equivalence of these two definitions, extending the famous result of Curtis-Hedlund-Lyndon’s theorem. Another physics-inspired symmetry is then added to the model, namely reversibility

Le calcul et la décidabilité du supremum de deux pseudo variétés de semi groupes est un problème difficile en dépit de son apparente simplicité. L'exemple le plus surprenant est du à Albert, Baldinger et Rhodes (1992): Le supremum de deux pseudo équationnelles de bases finies, donc décidables peut ne pas être décidable. À l'aide de la théorie des opérations implicites, nous résolvons deux problèmes ouverts de ce type proposés dans le traité d'Almeida semigrupos finitos e algebra universal, publicacoes do instituto de matematica e estatistica da universidade de Sao Paulo: d'une part, la pseudo variété j b n'est pas de base finie mais est décidable; d'autre part, une formulation explicite de la pseudo variété li b est donnée. Les preuves sont basées sur des arguments topologiques et algébriques d'une part, combinatoires d'autre part

Le sujet de cette thèse se divise en trois parties: les deux premières traitent chacune d'une extension du modèle utilisé en théorie des automates, tandis que la dernière aborde une partie plus concrète qui consiste à générer des automates avec des propriétés particulières. Tout d'abord, nous donnons une extension du concept d'automate universel, défini sur les mots finis, aux omega-langages. Pour cela, nous avons défini une forme normale pour tenir compte de la spécificité du mode d'acceptation des automates de Büchi qui nous permettent de reconnaître les omega-langages. Ensuite nous avons défini deux types d'omega-factorisations, "classiques" et "pures", qui sont des extensions du concept de factorisation d'un langage, ce qui nous a permis de définir l'automate universel d'un omega-langage. Nous avons prouvé que ce dernier dispose bien des différentes propriétés attendues: il est le plus petit automate de Büchi reconnaissant l'omega-langage et qui possède la propriété d'universalité (moyennant la forme normale). Nous présentons également une méthode pour calculer efficacement les omega-factorisations maximales d'un langage à partir d'un automate prophétique reconnaissant le dit langage. Dans la seconde partie, nous traitons le cas des automates bidirectionnels à multiplicité dans un semi-anneau. Dans un premier temps, nous donnons une version légérement différente de la construction permettant de passer d'un automate bidirectionnel à multiplicité à un automate unidirectionnel à multiplicité et nous prouvons qu'elle préserve la non-ambiguïté mais pas le déterminisme. Nous montrons, également à l'aide d'une construction, que les automates bidirectionnels à multiplicité non-ambigus sont équivalents aux automates unidirectionnels à multiplicité déterministes. Dans un second temps, nous nous concentrons sur les semi-anneaux tropicaux (ou min-+). Nous montrons que sur N-min-+, les automates bidirectionnels sont équivalents aux automates unidirectionnels. Nous montrons également que sur Z-min-+, les automates bidirectionnels n'ont pas toujours un comportement défini et que cette propriété est décidable tandis qu'il n'est pas décidable s'il existe un mot pour lequel le comportement est défini. Dans la dernière partie, nous proposons un algorithme de génération aléatoire d'automate acycliques, accessibles et déterministes ainsi que d'automates acycliques minimaux avec une distribution qui est quasiment uniforme, tout cela à l'aide de chaîne de Markov. Nous prouvons l'exactitude de chacun de ces deux algorithmes et nous expliquons comment adapter en tenant compte de contraintes sur l'ensemble des états finals
The subject of this thesis is decided into three parts: two of them are about extensions of the classical model in automata theory, whereas the third one is about a more concrete aspect which consists in randomly generate automata with specific properties. We first give an extension of the universal automaton on finite words to infinite words. To achieve this, we define a normal form in order to take account of the specific acceptance mode of Büchi automata which recognize omega-langages. Then we define two kinds of omega-factorizations, a "regular" one and the "pure" kind, which are both extensions of the classical concept of factorization of a language. This let us define the universal automaton of an omega-language. We prove that it has all the required properties: it is the smallest Buchi automaton, in normal form, that recognizes the omega-language and which has the universal property. We also give an effective way to compute the "regular" omega-factorizations of a language using a prophetic automaton recognizing the language. In the second part, we deal with two-way automata weighted over a semi ring. First, we give a slightly different version of the computation of a weighted one-way automaton from a weighted two-way automaton and we prove that it preserves the non-ambiguity but not the determinism. We prove that non-ambiguous weighted two-way automata are equivalent to deterministic weighted one-way automata. In a later part, we focus on tropical semi rings (or min-+). We prove that two-way automata on N-min-+ are equivalent to one-way automata on N-min-+. We also prove that the behavior of two-way automata on Z-min-+ are not always defined and that this property is decidable whereas it is undecidable whether or not there exists a word on which the behavior is defined. In the last section, we propose an algorithm in order to randomly generate acyclic, accessible and determinist automata and minimal acyclic automata with an almost uniform distribution using Morkov chains. We prove the reliability of both algorithms and we explain how to adapt them in order to fit with constraints on the set of final states

Des stations de mesure de la qualité de l’eau sont utilisées pour mesurer la qualité de l'eau à haute fréquence. Pour une gestion efficace de ces mesures, la qualité des données doit être vérifiée. Dans une méthode univariée précédemment développée, des points aberrants et des fautes étaient détectés dans les données mesurées par ces stations en employant des modèles à lissage exponentiel pour prédire les données au moment suivant avec l’intervalle de confiance. Dans la présente étude, ne considérant que le cas univarié, la détection de points aberrants est améliorée par l’identification d’un modèle autorégressif à moyenne mobile sur une fenêtre mobile de données pour prédire la donnée au moment suivant. Les données de turbidité mesurées à l'entrée d'une station d'épuration municipale au Danemark sont utilisées comme étude de cas pour comparer la performance de l’utilisation des deux modèles. Les résultats montrent que le nouveau modèle permet de prédire la donnée au moment suivant avec plus de précision. De plus, l’inclusion du nouveau modèle dans la méthode univariée présente une performance satisfaisante pour la détection de points aberrants et des fautes dans les données de l'étude de cas.
Water quality monitoring stations are used to measure water quality at high frequency. For effective data management, the quality of the data must be evaluated. In a previously developed univariate method both outliers and faults were detected in the data measured by these stations by using exponential smoothing models that give one-step ahead forecasts and their confidence intervals. In the present study, the outlier detection step of the univariate method is improved by identifying an auto-regressive moving average model for a moving window of data and forecasting one-step ahead. The turbidity data measured at the inlet of a municipal treatment plant in Denmark is used as case study to compare the performance of the use of the two models. The results show that the forecasts made by the new model are more accurate. Also, inclusion of the new forecasting model in the univariate method shows satisfactory performance for detecting outliers and faults in the case study data.

Nous étudions dans cette thèse des structures généralisant la notion classique de mot. Elles sont construites à partir d’un ensemble partiellement ordonné (partially ordered set ou poset) vérifiant les propriétés suivantes : — elles ne contiennent pas 4 éléments distincts x, y, z, t dont l’ordre relatif est exactement x < y, z < y, z < t (posets dits sans N) ; — les chaînes sont des ordres linéaires dénombrables et dispersés ; — les antichaînes sont finies ; et chaque élément est étiqueté par une lettre d’un alphabet fini. De manière équivalente, la classe des posets que nous considérons est la plus petite construite à partir du poset vide et du singleton, fermée par les produits séquentiel et parallèle finis, et le produit ω et son renversé −ω (posets série-parallèles). Elle est une généralisation à la fois des posets série-parallèles finis étiquetés, en y ajoutant l’infinitude, et des mots transfinis, en affaiblissant l’ordre total des éléments en ordre partiel. En informatique, les posets série-parallèles finis trouvent leur intérêt dans la modélisation des processus concurrents basés sur les primitives fork/join, et les mots transfinis dans l’étude de la récursivité. Les langages rationnels de ces posets étiquetés sont définis à partir d’expressions et d’automates équivalents introduits par Bedon et Rispal, qui généralisent le cas des mots transfinis (Bruyère et Carton) et celui des posets finis (Lodaya et Weil). Dans cette thèse nous les étudions du point de vue de la logique. Nous généralisons en particulier le théorème de Büchi, Elgot et Trakhtenbrot, établissant pour le cas des langages de mots finis l’égalité entre la classe des langages rationnels et celle des langages définissables en logique monadique du second ordre (MSO). La logique mise en oeuvre est une extension de MSO par de l’arithmétique de Presburger. Nous nous intéressons également à certaines variétés d’algèbres de posets. Nous montrons que l’algèbre dont l’univers est la classe des posets série-parallèles transfinis et dont les opérations sont les produits séquentiel et parallèle finis et les produits (resp. puissances) ω et − ω est libre dans la variété correspondante V (resp. V 0). Nous en déduisons la liberté de la même algèbre sans le produit parallèle ou le produit − ω. Enfin, nous montrons que la théorie équationnelle de V 0 est décidable. Ce sont notamment des généralisations de résultats similaires de Bloom et Choffrut pour la variété d’algèbres de mots de longueur inférieure à ω!, de Choffrut et Ésik pour la variété d’algèbres de posets sans N dont les antichaînes sont finies et les chaînes sont de longueur inférieure à ω! et ceux de Bloom et Ésik pour la variété d’algèbres de mots sur les ordres linéaires dénombrables et dispersés
We study in this thesis structures extending the classical notion of word. They are built from a partially ordered set (poset) verifying the following properties : — they do not contain 4 distinct elements x, y, z, t whose relative order is exactly x < y, z < y, z < t (posets called N-free) ; — their chains are countable and scattered linear orderings ; — their antichains are finite ; and each element is labeled by a letter of a finite alphabet. Equivalently, the class of posets which we consider is the smallest one built from the empty poset and the singleton, and being closed under sequential and parallel products, and ω product and its backward ordering −ω (series-parallel posets). It is a generalization of both of finite series-parallel labeled posets, by adding infinity, and transfinite words, by weakening the total ordering of the elements to a partial ordering. In computer science, series-parallel posets find their interest in modeling concurrent processes based on fork/join primitives, and transfinite words in the study of recursion. The rational languages of these labeled posets are defined from expressions and equivalent automata introduced by Bedon and Rispal, which generalize thecase of transfinite words (Bruyère and Carton) and the one of finite posets (Lodaya and Weil). In this thesis we study such structures from the logic point of view. In particular, we generalize the Büchi-Elgot-Trakhtenbrot theorem, establishing in the case of finite words the correspondence between the class of rational languages and the one of languages definable in monadic second order logic (MSO). The implemented logic is an extension of MSO by Presburger arithmetic. We focus on some varieties of posets algebras too. We show that the algebra whose universe is the class of transfinite series-parallel posets and whose operations are the sequential and parallel products and the ω and −ω products (resp. powers) is free in the corresponding variety V (resp. V 0). We deduce the freeness of the same algebra without parallel or −ω product. Finally, we showthat the equational theory of V 0 is decidable. These results are, in particular, generalizations of similar results of Bloom and Choffrut on the variety of algebras of words whose length are less than ω!, of Choffrut and Ésik on the variety of algebras of N-free posets whose antichains are finite and whose chains are less than ω! and those of Bloom and Ésik on the variety of algebras of words indexed by countable and scattered linear orderings

L'operation zigzag et l'operation de mots de pile sont deux extensions de l'etoile de kleene. Nous en etudions les structures et diverses proprietes. Les notions de code zigzag et de pile-code sont montrees decidables dans le cas rationnel. Dans le cadre de l'operation zigzag, sont etudiees plusieurs proprietes de z-stabilite ainsi que la notion d'enveloppe z-libre. Les problemes de reconnaissance par monoides finis ou infinis sont abordes pour les deux operations. Enfin, nous developpons une version binaire de l'operation zigzag

Nous nous intéressons à la vérification de systèmes concurrents tels que les automates communicants et les réseaux de Petri. La vérification de tels systèmes est difficile parce que la présence des composants concurrents augmente de façon importante le nombre des états globaux. Divers techniques ont été proposées pour combattre ce phénomène d'explosion combinatoire. Dans cette thèse, nous nous concentrons sur la technique de dépliage de réseau de Petri. Cette technique tire parti de l'indépendance des actions pour donner une représentation concise des états d'un réseau de Petri. De nombreux travaux ont été réalisés dans ce domaine, mais les aspects d'implémentation ont été souvent négligés. A partir d'une étude expérimentale, nous mettons en avant les parties critiques d'un algorithme de dépliage. Nous proposons de nouvelles stratégies pour diminuer le temps et ccupation-mémoire du calcul. Certaines sont basées sur des techniques de cache et d'autres réduisent le nombre d'appels aux fonctions critiques. Nous introduisons ensuite un nouveau modèle: le produit de réseaux de Petri symétriques. Il nous permet d'effectuer le dépliage de façon modulaire. Nous l'appliquons au produit d'automates. Et les symétries nous permettent d'utiliser des files non bornées. Ces travaux aboutissent à la réalisation d'un outil, l'outil KissPN.

Cette thèse traite de certains aspects de la logique Monadique du Second Ordre sur les mots infinis (MSO) à travers le prisme de la théorie de la démonstration.Elle contient deux parties distinctes.La première étudie des variantes intuitionistes de MSO avec de fortes propriétés du témoin qui permettent d’extraire des fonctions synchrones à partir de dérivations formelles.Un sous-système constructif avec la propriété du témoin est défini et est prouvé correct et complet pour la synthèse de Church. Pour ce faire, la correspondance entre formules de MSO et automates est raffinée pour donner une sémantique du système constructif où les preuves correspondent à une notion de simulation entre automates non-déterministes. Cette notion est étendue aux automates alternants. Cela mène à un sous-système de MSO plus fin basé sur la logique linéaire. Un théorème de complétude plus fort est montré pour ce dernier reposant sur la détermination des jeux ω-réguliers et une interprétation des formules similaire à la traduction Dialectica de Gödel.La seconde partie s’intéresse à la force axiomatique du théorème de décidabilité de MSO sur les mots infinis et autres résultats afférents de théorie des automates sur les mots infinis dans le cadre des mathématiques à rebours.On montre entre autres une équivalence entre la décidabilité de MSO, la version additive du théorème de Ramsey pour les paires et le principe de récurrence pour les formules Σ⁰₂ dans la théorie RCA₀. On conclut cette partie avec quelques résultats préliminaires concernant la décidabilité de MSO sur les rationnels, qui établissent que des axiomes strictement plus forts sont nécessaires dans ce cas
This thesis studies certain aspects of Monadic Second-Order logic over infinitewords (MSO) through the lens of proof-theory. It is split into two independentparts.The first parts studies intuitionistic variants of MSO with strong witnessing properties allowing the extraction of synchronous functions from formal proof derivations.A constructive system with a suitable witnessing property is defined and proven correct and complete with respect to Church’s synthesis. To this end, the usual correspondence between MSO formulas and automata is refined to give a semantics of the constructive subsystem where proofs are correspond to simulations between non-deterministic automata. This notion is extended toalternating automata. This leads to a finer-grained system based on linear logicand MSO, which is then approached similarly. A stronger completeness theoremis shown for this latter system; the proof requires the determination of ω-regular games and an interpretation of linear formulas reminiscent of Gödel’sDialectica.The second part of this thesis is concerned with the axiomatic strength of the decidability theorem for MSO over infinite words and related results on infinite word automata. We proveamong other things an equivalence between the decidability of MSO, the additive version ofRamsey’s theorem for pairs and the principle of Σ⁰₂-induction over the weak artithmetical theoryRCA₀. We conclude this part by collecting a few results concerning the decidability of MSO overrationals, showing that axioms beyond Σ⁰₂-induction are necessary in that case

Ce travail de thèse étudie la complexité des pavages et des automates cellulaires. L'analyse débute par des considérations structurelles : la quasipériodicité des pavages. A tout ensemble de tuiles qui pave le plan, on associe une fonction de quasipériodicité qui quantifie sa complexité. Tout d'abord, on montre que toute fonction "raisonnable" peut être capturée par un ensemble de tuiles et qu'il existe des pavages dont la fonction de quasipériodicité croît plus rapidement que n'importe quelle fonction récursive. Ensuite, on démontre un théorème de Rice pour les pavages : l'ensemble des ensembles de tuiles qui admettent les mêmes pavages qu'un autre fixé est indécidable et récursivement énumérable. Enfin, on transpose notre résultat dans le contexte des automates cellulaires. La seconde partie de notre travail concerne l'étude des automates cellulaires sous l'angle des systèmes dynamiques, et plus particulièrement des automates chaotiques. Les définitions usuelles classifiant les automates chaotiques ne sont pas satisfaisantes. Pour palier ce problème, on utilise deux nouvelles topologies. La première est dite de Besicovitch, et permet de supprimer la prédominance du motif central lors de l'étude de l'évolution de l'automate. On apporte plusieurs résultats, les premiers indiquant que notre nouvel espace de travail est acceptable à l'étude des automates cellulaires, en tant que systèmes dynamiques ; les seconds montrent que la notion de chaos subsiste, grâce à la définition de sensibilité aux conditions initiales, mais que les classes plus chaotiques sont vides. La seconde topologie employée est définie à l'aide de la complexité algorithmique. Le but de cette approche est d'avoir une distance qui traduit la facilité à calculer un élément à l'aide de l'autre. Nos résultats complètent les précédents. Ils attestent de manière formelle que les automates cellulaires ne peuvent pas modifier continûment l'information contenue dans une configuration, et surtout qu'ils sont incapables d'en créer

Cette thèse revisite les problèmes d'accessibilité et de vivacité pour les au-tomates temporisés.L'accessibilité est couramment résolue par le calcul d'un arbre de recherche abstrait. L'abstraction est paramétrée par des bornes provenant des gardes de l'automate. Nous montrons que l'abstraction a 4LU de Behrmann et al. est la plus grande abstraction saine et complète pour les bornes LU. N' étant pas convexe, elle n'est pas mise en oeuvre dans les outils. Nous introduisons une méthode qui permet son utilisation éfficace. Finalement, nous proposons une optimisation des bornes à la volée exploitant le calcul de l'arbre.Le problème de vivacité requiert de détecter les exécutions Zenon/non-Zenon. Une solution standard ajoute une horloge à l'automate. Nous montrons qu'elle conduit a une explosion combinatoire. Nous proposons une solution qui évite ce problème pour une grande classe d'abstractions. Pour les abstractions LU nous montrons que détecter ces exécutions est un problèmeNP-complet
We consider the classic model of timed automata introduced by Alurand Dill. Two fundamental properties one would like to check in this modelare reachability and liveness. This thesis revisits these classical problems.The reachability problem for timed automata asks if there exists a run ofthe automaton from the initial state to a given final state. The standard solutionto this problem constructs a search tree whose nodes are abstractionsof zones. For effectiveness, abstractions are parameterized by maximal lowerand upper bounds (LU-bounds) occurring in the guards of the automaton.Such abstractions are also termed as LU-abstractions. The a4LU abstractiondefined by Behrmann et al is the coarsest known LU-abstraction. Althoughit is potentially most productive to use the a4LU abstraction, it has not beenused in implementations as it could lead to non-convex sets. We show howone could use the a4LU abstraction efficiently in implementations. Moreover,we prove that a4LU abstraction is optimal: given only the LU-bound information,it is the coarsest possible abstraction that is sound and completefor reachability. We then concentrate on ways to get better LU-bounds. Inthe standard procedure the LU-bounds are obtained from a static analysisof the automaton. We propose a new method to obtain better LU-boundson-the-fly during exploration of the zone graph. The potential gains of proposedimprovements are validated by experimental results on some standardverification case studies.The liveness problem deals with infinite executions of timed automata.An infinite execution is said to be Zeno if it spans only a finite amountof time. Such runs are considered unrealistic. While considering infiniteexecutions, one has to eliminate Zeno runs or dually, find runs that arenon-Zeno. The B¨uchi non-emptiness problem for timed automata asks ifthere exists a non-Zeno run visiting an accepting state infinitely often. Thestandard solution to this problem adds an extra clock to take care of non-Zenoness. We show that this solution might lead to an exponential blowupin the search space. We propose a method avoiding this blowup for a wideclass of abstractions weaker than LU-abstractions. We show that such amethod does not exist for LU-abstractions unless P=NP. Another questionrelated to infinite executions of timed automata is to decide the existenceof Zeno runs. We provide the first complete solution to this problem. Itworks for a wide class of abstractions weaker than LU. Yet again, we showthe solution could lead to a blowup for LU-abstractions, unless P=NP

Les travaux présentés dans cette thèse portent sur des problématiques de modélisation mathématique de lutte biologique augmentative et des recommandations pratiques qui en sont dérivées. La lutte biologique est une méthode de phytoprotection visant à combattre les ravageurs des cultures à l'aide de leurs ennemis naturels ; son développement est crucial en vue de diminuer l'utilisation de pesticides dont les conséquences néfastes sont reconnues, notamment sur la santé des agriculteurs et des consommateurs, mais aussi sur l'environnement. Il est donc nécessaire de proposer et développer des méthodes de lutte biologique efficaces. Dans cette thèse, nous nous intéressons plus particulièrement à la lutte biologique augmentative, qui consiste à lâcher périodiquement des ennemis naturels qui n'ont pas la capacité de s'établir dans l'environnement en l'absence des ravageurs cibles. Nous introduisons une famille générique de modèles représentant d'une part la relation proie / prédateur à la base de la lutte biologique sous forme d'événements discrets. Nous précisons ensuite ce modèle pour diverses situations rencontrées dans le cadre de la lutte biologique et indiquons quelles en sont les conséquences sur les stratégies de déploiements des ennemis naturels : nous étudions notamment l'effet d'interférences entre prédateurs pour l'accès aux proies, l'existence de relations de cannibalisme entre prédateurs et les conséquences que peuvent avoir des récoltes partielles des plantes sur l'efficacité de la lutte biologique. Enfin, nous résumons tous nos résultats sous forme de recommandations pratiques pour la lutte biologique et en présentons une validation expérimentale sur un exemple agronomique d'intérêt, dans lequel les prédateurs entretiennent des relations d'interférence.

L'objet de cette thèse est la formulation et l'étude de modèles proie-prédateur avec une structure en taille du prédateur, afin de décrire les populations de phytoplancton et zooplancton. Cette étude a été motivée par les données collectées par le Laboratoire d'Océanographie de Villefranche-Sur-Mer dont l'évolution depuis 1966 du spectre de taille du zooplancton dans la baie de Villefranche. Dans une première partie nous présentons les diverses données collectées et proposons différents modèles dans un cadre assez général, ayant soit une structure continue donnant lieu à une équation aux dérivées partielles couplée avec une équation différentielle ordinaire, ou soit une structure discrète, pouvant correspondre à des stades de développement et donnant lieu à un système d'équations différentielles ordinaires. Ensuite une étude mathématique de ces modèles est faite pour certains cas particuliers (stabilité des équilibres, stabilisation d'un équilibre par un contrôle positif). Le cannibalisme étant présent au sein du zooplancton, nous mettons l'accent sur son étude, notamment sur un modèle comprenant deux classes de taille de prédateurs. Nous montrons que le cannibalisme peut stabiliser la dynamique ou encore être une stratégie évolutionnairement stable. Finalement nous tentons de confronter numériquement ces modèles aux données : les simulations donnent des résultats qualitativement proches des observations.

Les quatres chapîtres de cette thèse aborde quatre thèmes de la théorie des itérations: 1) nous élaborons un algorithme de vérification de l'attraction d'un point fixe d'une itération discrète dans son voisinage second. Cet algorithme est comparé aux conditions nécessaires et suffisantes énoncées par F. Robert avant d'être généralisé à d'autres attracteurs et d'autres bassins d'attraction. 2) Après un tour d'horizon des méthodes de calcul de racines pième de matrices réelles nous proposons un algorithme de calcul de racines carrées de matrices booléennes quelconques. 3) Nous utilisons un opérateur monotone pour étudier les itérations bloc-séquentielles de réseaux à seuil: on caractérise ainsi leurs dynamiques. Nous étendons ces méthodes aux fonctions majorité et verres de spin généralisés. 4) Après avoir comparé les différents outils d'observation des dynamiques des réseaux booléens aléatoires d'interconnectivité 2, nous proposons une approche basée sur le calcul d'une approximation de chacune des 3 composantes: le coeur stable du réseau, le coeur oscillant, les paliers (notion introduite ici). En application nous nous intéressons au problème de la reconnaissance de séquences booléennes par ce type de réseaux

La compatibilité électromagnétique (CEM) des composants électroniques est devenue indispensable pour la conception des systèmes embarqués microélectroniques. Les modèles CEM aident les concepteurs de circuits à comprendre le comportement du système avant même sa fabrication. Dans ce contexte, un modèle électromagnétique générique des émissions rayonnées, optimisé et compatible avec la modélisation des dispositifs microélectroniques miniatures a été développé. L’architecture de base de ce modèle a été inspirée du modèle du champ magnétique développé antérieurement à l’IRSEEM. Dans un premier temps un modèle mono-fréquence capable de reproduire et de prévoir le champ électromagnétique rayonné au-dessus d’un dispositif électronique sous test a été développé. Un réseau de dipôles électriques élémentaires associé à une nouvelle méthode d’extraction incorporant un algorithme d’optimisation non-linéaire, sont mis en oeuvre. Le rôle de la permittivité relative du dispositif sous test est pris en compte dans la procédure de modélisation. Le modèle a été validé sur plusieurs composants micro-ondes classiques, miniatures et circuits « on-chip ». L’optimisation mathématique du modèle l’a rendu plus robuste et par conséquent applicable aux dispositifs complexes. Le nouveau concept a été validé sur deux cas de test. Deuxièmement, le modèle mono-fréquence a été étendu afin de prédire le champ électromagnétique large-bande et, par conséquent, le champ dans le domaine temporel. La méthode de série de Fourier est utilisée pour transférer les données du domaine fréquentiel vers le domaine temporel. Le principe de modélisation a été validé par des simulations effectuées avec un logiciel électromagnétique 3D. Enfin, un environnement convivial de modélisation (outil) a été développé
With component level electromagnetic compatibility (EMC) taking the front stage in design of embedded microelectronic systems, EMC models help circuit designers in understanding the behavior of the system even before its fabrication. In this context, generic electromagnetic emission models, optimized and compatible to modeling miniature microelectronic devices, are developed. The basic architecture of the models has been inspired from a previously existing magnetic field model developed in IRSEEM. First, a mono-frequency model capable of reproducing and predicting the radiated electromagnetic fields above any device is developed. A set of elementary electric dipole is used to represent the model and a state-of-the art extraction method, incorporating a non-linear optimization algorithm, is implemented in order to extract the model parameters. The role of the effective relative permittivity of the DUT is taken into account in the modeling procedure. The model has been validated on several conventional microwave components, miniature and “on-chip” devices. The computational performance of the model is then optimized and made robust suitable for application to complex devices. As a proof of concept, the method is validated on a couple of test cases. Second, the monofrequency model is extended toward predicting the large-band electromagnetic fields and thereby the time-harmonic fields. Fourier series based method is used for transforming the wide-band frequency data into time-domain. The modeling principle is validated with time-domain simulations performed in a 3D electromagnetic software. Finally, an integrated development environment has been developed in order to facilitate the use of the developed emission models. The menu-based intuitive tool provides the right environment for engineers and designers to use and test the models for specialized applications

Cette thèse porte sur certaines extensions des automates pondérés, et étudie les séries qu’ils réalisent en fonction de la nature des poids.Ces extensions se distinguent par les mouvements supplémentaires autorisés à la tête de lecture de l’automate : retour au début du mot pour les automates circulaires, changement de sens de lecture pour les automates boustrophédons.Dans le cas général, les automates pondérés circulaires sont plus puissants que les automates unidirectionnels classiques, et moins puissants que les boustrophédons.On introduit de plus les expressions de Hadamard, qui sont une extension des expressions rationnelles et qui permettent de dénoter le comportement des automates circulaires. Les aspects algorithmiques de cette conversion sont étudiés dans le cas où les poids appartiennent à un semi-anneau rationnellement additif.On montre que lorsque les poids sont des nombres rationnels, réels ou complexes, les automates circulaires sont aussi expressifs que les boustrophédons.Enfin, si les poids forment un bi-monoïde localement fini, les automates boustrophédons ne sont pas plus expressifs que les automates pondérés classsiques
This thesis deals with some extensions of weighted automata,and studies the series they can realisedepending on the nature of their weigths.These extensions are characterised by howthe input head of the automaton is allowed to move:rotating automata can go back at the beginning of the word,and two-way automata can change the reading direction.In the general setting, weigthed rotating automata are morepowerful than classical one-way automata, and less powerfulthan two-way ones.Moreover, we introduce Hadamard expressions,which are an extension of rational expressions and can denotethe behaviour of rotating automata.The algorithms for this conversion are studied when the weights belong toa rationally additive semiring.Then, rotating automata are shown as expressive as two-way automatain the case of rational, real or complex numbers.It is also proved that two-way and one-way automataare equivalent when weighted on a locally finite bimonoid

Un automate cellulaire, dans sa forme la plus generale, est un ensemble infini d'automates finis interconnectes suivant un reseau regulier et evoluant de facon synchrone au cours du temps. Issus des travaux de john von neumann sur l'auto-reproduction (1950), ils ont connu, ces dernieres annees un nombre croissant d'applications en informatique et en physique theorique. Ce travail est subdivise en trois chapitres: une presentation generale couvrant l'essentiel de l'etat actuel de la recherche au sujet des a. C. Dans le domaine de l'informatique theorique, la presentation d'une preuve originale du theoreme d'acceleration lineaire pour les a. C. Unidimensionnels accepteurs de langages et une derniere partie consacree a un modele derive des a. C. : les automates treillis. Cette partie contient, notamment, l'etude, par des moyens algebriques, de la classe particuliere des automates treillis superposables

La vérification formelle de programmes consiste à raisonner rigoureusement, à l'aide de logiques mathématiques sur des programmes informatiques afin de démontrer leur validité vis-à-vis d'une certaine spécification. Cela permet d'obtenir une très forte assurance d'absence de bug. Le choix du cadre logique dans lequel effectuer la vérification d'un programme est dicté par deux impératifs: la logique doit être suffisamment expressive pour exprimer la spécification voulue et rendre compte de chacune des instructions du programme; et elle doit être suffisamment peu complexe, afin de pouvoir automatiser autant que possible (et en temps raisonable), le processus de vérification. Dans cette thèse, nous étudions deux types de logiques et comment les manipuler pour la vérification formelle. D'abord 1 logique du premier ordre sur les structures automatiques, par exemple l'Arithmétique de Presburger, qui permet d'exprimer des propriétés sur les entiers. Nous montrons qu'elles peuvent être efficacement représentées et manipulées avec des automates, typiquement nous détaillons un algorithme générique basé sur les automates qui permet de décider entre autres l'Arithmétique de Presburger avec une complexité proche de sa difficulté. Ensuite, nous présentons des transducteurs finis avec des registres en écriture seule, et étudions leur pouvoir expressif. Nous verrons qu'ils sont une extension élégante des automates finis pour définir des transformations de mots, étant un modèle calculatoire simple et intuitif, et nous établissons qu'ils permettent d'implémenter les transformations définissables par la logique monadique du second ordre
Formal software verification consists in a rigorous analysis of programs using mathematical logic, in order to demonstrat they meet their specification, and ensure with strong confidence in the absence of bugs. The choice of the logical framework to perform the analysis is crucial, and must address two issues: not only must the logic be expressive enough to express the specification and reflect the action of each instruction, but also the logic formalism must be simple enough in order to automate efficiently as much as possible the verification process. In this thesis we will study two logical frameworks and show how to manipulate those. First we will focus on first-order logics over automatic structures, such as Presburger Arithmetics which allows to express properties about integers. We will show that formulas can be effectively represented as automata, and we will detail a generic automata-based algorithn that allow to decide such first-order logics, whose complexity closely matches the hardness of those logics. Then we will present streaming string transducers, which are automata with a finite number of write-only registers and we will inspect their expressiveness. We will present this elegant extension of finite state automata to define string transformations as an intuitive computational model and we will establish their expressive power is precisely express transformations definable by monadic second-order logics

Les automates à contraintes (automates imposant des égalités et différences entre sous-termes), la réécriture de termes et les contraintes ensemblistes (inclusions entre expressions désignant des ensembles de termes finis) sont les domaines d'étude de cette thèse. Le point de départ de nos travaux est la recherche d'outils de décision les plus puissants possibles. Nous définissons tout d'abord un nouvel outil d'indécidabilité nous permettant de montrer un résultat d'indécidabilité dans chacun des domaines cites ci-dessus : la structure finie de la grille. Ces résultats concernent le problème du vide pour les automates à tests entre cousins (sous-termes à la profondeur 2), la décidabilité de la théorie du premier ordre de la réécriture en un pas et la décidabilité de la théorie du premier ordre des contraintes ensemblistes
Ensuite, nous montrons la décidabilité du fragment existentiel de la réécriture en un pas pour une classe restreinte de systèmes de réécriture et la décidabilité du problème de satisfiabilité pour les systèmes de contraintes ensemblistes positives avec tests d'égalité. Par la suite, nous prouvons la décidabilité du problème de reconnaissabilité pour la classe des langages reconnus par automates à tests entre frères (sous-termes à la profondeur 1), c'est-à-dire que pour tout langage l de cette classe, on peut décider si l est régulier ou non. Dans le domaine de la réécriture, nous étudions le langage R*(l) où R est un système de réécriture et L un langage régulier, et les questions de décision « Rel(L1) inclus dans L2 ? » Et « Rel(L1) = L2 ? » où L1 et L2 sont des langages réguliers et Rel(L1) est l'image de L1 par une relation Rel. Finalement, nous prouvons par une étude topologique que le pouvoir d'expression en terme d'ensembles de solutions des contraintes ensemblistes positives avec symboles de projection est strictement supérieur à celui des contraintes ensemblistes positives et négatives sans symbole de projection

Nous etudions les automates cellulaires depuis plusieurs points de vue. Nous commencons par les envisager comme des systemes dynamiques et presentons une nouvelle preuve d'un resultat celebre du a richardson: les automates cellulaires sont exactement les fonctions continues qui commutent avec les translations. Cette preuve nous permet d'etudier la minimisation de la representation des automates cellulaires. Ensuite, nous presentons une classification des automates cellulaires en fonction de leur comportement limite, classification que nous prouvons etre partiellement decidable en dimension 1. Nous montrons aussi une extension en termes de probabilites d'un theoreme du a karel culik en 1989. Les methodes utilisees relevent de la topologie et de la combinatoire. La deuxieme partie est plus tournee vers l'algorithmique et la complexite. Nous y presentons deux reductions de problemes de pavages en problemes concernant les automates cellulaires. A l'aide de ces reductions, nous montrons simplement que la surjectivite des automates cellulaires est indecidable en dimension deux (theoreme du a jarkko kari en 1989) ainsi que la co-np-completude et la co-np-completude en moyenne des problemes de decision suivants: - etant donne un automate cellulaire en dimension 2, est-il bijectif quand il est restreint aux configurations finies plus petites que sa taille? - etant donne un automate cellulaire en dimension 2, est-il bijectif quand il est restreint aux configurations periodiques de periode inferieure a sa taille?

La 1ère partie traite des automates boustrophédons, du semi-groupe de Birget et du monoïde inversif libre. La 2ème partie étudie le comportement infini d'un automate boustrophédon, la 3ème partie est consacrée aux variétés de semi-groupes et aux mots infinis. La 4ème partie poursuit la classification des langages rationnels de mots infinis à l'aide des variétés des semi-groupes

Vers 1965 achève de se constituer, sous le nom de "théorie des automates", une étude logico-algébrique des dispositifs de calcul pouvant servir comme modelés mathématiques de machines traitant l'information. Théoriquement liée à la machine de Turing, l'entreprise ne se thématise pourtant que vers 1948, quand Von Neumann propose de traiter en une théorie "logique" générale des questions issues de préoccupations hétéroclites, de la biologie a la technique des ordinateurs. C'est alors l'étude des automates finis qui, dans la décennie 1950-1960, organise la première ces apports disparates en une doctrine abstraite cohérente pourvue d'outils algébriques et logiques maniables. Parallèlement l'approche de Turing de la calculabilité suscite, en regard de la théorie des automates finis, une théorie des machines infinies (dont l'architecture est progressivement rapprochée de celle des machines réelles), que prolonge bientôt une théorie de la complexité de calcul. Enfin, autour de 1960, rejoignant la tradition combinatoire-algorithmique de post et Markov, l'analyse syntaxique des langues naturelles et des langages de programmation a donné l'impulsion décisive, via la théorie des grammaires formelles, à l'étude d'automates "infinis-limites", automates à pile et automates linéairement bornes notamment
In the years 1965, the process of the constitution of the "theory of automata", a logico-algebraical study of the computing devices which can be used as mathematical models for information processing machines, was completed. In spite of its theoretical connection with the Turing machine, the enterprise did, however, not take the form of an explicit topic until 1948, when Von Neumann proposed to handle within the framework of a general "logical" theory a whole set of questions stemming from various domains, spreading from biology to computers. The study of finite automata, in the decade 1950-1960, was then the first to impose an organisation on these disconnected achievements in the form of a coherent abstract theory, endowed with manageable algebraical and logical tools. As a counterpart, Turing's approach of calculability gave rise to a theory of infinite machines (whose architectonics was brought gradually closer to that of actual machines), which was to be quickly extended by a computational complexity theory. Finally, in the sixties, joining the combinatorial-algorithmic tradition of post and Markov, the syntactical analysis of natural and programming languages gave the decisive impulse, through the theory of formal grammars, to the study of "bounded-infinite" automata, in particular pushdown and linear bounded automata

Cette thèse traite des ensembles rationnels de mots indexés par des ordres linéaires et en particulier du problème de la fermeture par complémentation. Dans un papier fondateur de 1956, Kleene initie la théorie des langages en montrant que les automates sur les mots finis et les expressions rationnelles ont le même pouvoir d'expression. Depuis, ce résultat a été étendu à de nombreuses structures telles que les mots infinis (Büchi, Muller), bi-infinis (Beauquier, Nivat, Perrin), les mots indexés par des ordinaux (Büchi, Bedon), les traces, les arbres... Plus récemment, Bruyère et Carton ont introduit des automates acceptant des mots indexés par des ordres linéaires et des expressions rationnelles correspondantes. Ces structures linéaires comprennent les mots infinis, les mots indexés par des ordinaux et leurs miroirs. Le théorème de Kleene a été généralisé aux mots indexés par les ordres linéaires dénombrables et dispersés, c'est-à-dire les ordres ne contenant pas de sous-ordre isomorphe à Q. Pour la plupart des structures, la classe des ensembles rationnels forme une algèbre de Boole. Cette propriété est nécessaire pour traduire une logique en automates. La fermeture par complémentation restait un problème ouvert. Dans cette thèse, on résout ce problème de façon positive: on montre que le complément d'un ensemble rationnel de mots indexés par des ordres linéaires dispersés est rationnel. La méthode classique pour obtenir un automate acceptant le complémentaire d'un ensemble rationnel se fait par déterminisation. Nous montrons que cette méthode ne peut-être appliquée dans notre cas: tout automate n'est pas nécessairement équivalent à un automate déterministe. Nous avons utilisé d'autres approches. Dans un premier temps, nous généralisons la preuve de Büchi, basée sur une congruence de mots, et obtenons ainsi la fermeture par complémentation dans le cas des ordres linéaires de rang fini. Pour obtenir le résultat dans le cas général, nous utilisons l'approche algébrique. Nous développons une structure algébrique qui étend la reconnaissance classique par semigroupes finis : les semigroupes sont remplacés par les diamant-semigroupes qui possèdent un produit généralisé. Nous prouvons qu'un ensemble est rationnel si et seulement s'il est reconnu par un diamant-semigroupe fini. Nous montrons aussi qu'un diamant-semigroupe canonique, appelé diamant-semigroupe syntaxique, peut être associé à chaque ensemble rationnel. Notre preuve de la complémentation est effective. Le théorème de Schützenberger établit qu'un ensemble de mots finis est sans étoile si et seulement si son semigroupe syntaxique est fini et apériodique. Pour finir, nous étendons partiellement ce résultat au cas des ordres de rang fini.

Deux notions de réseaux d'automates apparaissent souvent dans la littérature. Les automates cellulaires, automates finis placés sur les sommets de z, z#2,, z#n, et qui communiquent suivant les directions principales de l'espace. La seconde notion est celle de graphe d'automates ou, aux sommets d'un graphe quelconque de degré borne, on place des automates finis qui communiquent par les arêtes. La première notion ne fonctionne que sur des graphes très pauvres, la seconde pose le problème suivant : les cellules ne connaissent pas l'allure du graphe autour d'elles. Voila pourquoi nous avons décidé d'étudier les automates cellulaires définis sur des graphes de Cayley qui sont des graphes modulaires régulièrement coloriés par des générateurs d'un groupe de présentation finie. Notre thèse comporte trois parties: dans la première, nous généralisons la notion d'automates cellulaires unidirectionnels sur les graphes de Cayley. Nous donnons des résultats sur la vitesse de simulation d'un automate cellulaire par un automate cellulaire unidirectionnel dans le cas de graphes usuels, en particulier, les graphes hexagonaux et triangulaires. Nous donnons dans le cas général des conditions nécessaires et des conditions suffisantes pour que de telles simulations soient possibles sur des graphes de Cayley quelconques. Dans la seconde partie, nous étudions la notion de simulation d'un réseau d'automates par un autre. Cette notion est relativement difficile à cerner, nous l'étudions pour les automates cellulaires définis sur les graphes de Cayley correspondants aux pavages archimédiens. Cela nous amène à montrer que tous ces graphes sont équivalents à la grille dans le plan. Nous donnons aussi des conditions suffisantes pour l'existence de telles simulations en terme de morphismes à noyau fini et de morphismes presque surjectifs. Nous étudions aussi les cas de structures finies et périodiques comme les tores d'automates généralisés. Dans la dernière partie, nous montrons comment synchroniser des chemins de longueur minimale entre deux points d'un graphe de Cayley. Pour cela, une difficulté algorithmique apparaît, elle est due à l'apparition de culs-de-sac dans le graphe de Cayley, c'est-à-dire de points à distance n de l'origine dont aucun des voisins n'est à distance n + 1

On considère des jeux stochastiques joués sur un graphe fini. La première partie s’intéresse aux jeux stochastiques à deux joueurs et information parfaite. Dans de tels jeux, les joueurs choisissent des actions dans ensemble fini, tour à tour, pour une durée infinie, produisant une histoire infinie. Le but du jeu est donné par une fonction d’utilité qui associe un réel à chaque histoire, la fonction est bornée et Borel-mesurable. Le premier joueur veut maximiser l’utilité espérée, et le deuxième joueur veut la minimiser. On démontre que si la fonction d’utilité est à la fois shift-invariant et submixing alors le jeu est semi-positionnel. C’est-à-dire le premier joueur a une stratégie optimale qui est déterministe et sans mémoire. Les deux joueurs ont information parfaite: ils choisissent leurs actions en ayant une connaissance parfaite de toute l’histoire. Dans la deuxième partie, on étudie des jeux de durée fini où le joueur protagoniste a zéro information. C’est-à-dire qu’il ne reçoit aucune information sur le déroulement du jeu, par conséquent sa stratégie est un mot fini sur l’ensemble des actions. Un automates probabiliste peut être considéré comme un tel jeu qui a un seul joueur. Tout d’abord, on compare deux classes d’automates probabilistes pour lesquelles le problème de valeur 1 est décidable: les automates leaktight et les automates simples. On prouve que la classe des automates simples est un sous-ensemble strict de la classe des automates leaktight. Puis, on considère des jeux semi-aveugles, qui sont des jeux à deux joueurs où le maximiseur a zéro information, et le minimiseur est parfaitement informé. On définit la classe des jeux semi-aveugles leaktight et on montre que le problème d’accessibilité maxmin est décidable sur cette classe
We consider stochastic games that are played on finite graphs. The subject of the first part are two-player stochastic games with perfect information. In such games the two players take turns choosing actions from a finite set, for an infinite duration, resulting in an infinite play. The objective of the game is given by a Borel-measurable and bounded payoff function that maps infinite plays to real numbers. The first player wants to maximize the expected payoff, and the second player has the opposite objective, that of minimizing the expected payoff. We prove that if the payoff function is both shift-invariant and submixing then the game is half-positional. This means that the first player has an optimal strategy that is at the same time pure and memoryless. Both players have perfect information, so the actions are chosen based on the whole history. In the second part we study finite-duration games where the protagonist player has zero information. That is, he gets no feedback from the game and consequently his strategy is a finite word over the set of actions. Probabilistic finite automata can be seen as an example of such a game that has only a single player. First we compare two classes of probabilistic automata: leaktight automata and simple automata, for which the value 1 problem is known to be decidable. We prove that simple automata are a strict subset of leaktight automata. Then we consider half-blind games, which are two player games where the maximizer has zero information and the minimizer is perfectly informed. We define the class of leaktight half-blind games and prove that it has a decidable maxmin reachability problem

Dans cette thèse, nous nous appliquons à étendre les liens entre les modèles de représentation des langage rationnels que sont les automates, la logique et les monoïdes au travers de deux extensions de ces théories. La première contribution concerne les transducteurs bidirectionnels, qui sont une extension des automates, définissant des transformations de mots. Nous proposons tout d'abord la construction du monoïde de transitions des machines bidirectionnelles. Cela nous permet ensuite de définir la notion de transducteurs bidirectionnels apériodiques. Nous prouvons finalement la stabilité de cette classe par composition. La seconde contribution concerne la logique sur mots finis. Le problème de la définissabilité d'un fragment logique est de pouvoir décider si un langage est définissable par une formule de ce fragment. Nous étudions la décidabilité de cette question lorsqu'un fragment voit sa signature enrichie, ici par des prédicats traitant de l'information modulaire des positions. Grâce à des méthodes algébriques, nous obtenons des résultats de transfert de décidabilité vers les fragments enrichis, unifiant d'anciens résultats connus, tout en en obtenant de nouveaux
In this thesis, we extend the links between the different models of representation of rational languages that are automata, logic and monoids through two extensions of these theories. The first contribution concerns the two-way transducers, an extension of automata defining transformations of words. We first propound the construction of the transitions monoid of two-way machines. This allows us to define the notion of aperiodic two-way transducers. We finally prove that this class is stable by composition. The second contribution concerns logic on finite words. The definability problem of a fragment of logic consists in deciding whether a given regular language can be defined by a formula of the said fragment. We study the decidability of this question when the signature of a fragment is enriched, in our case by predicates handling the modular information of the positions. Thanks to algebraic methods, we were able to gather transfer results to enriched fragments, unifying known results as well as obtaining new ones

Cette these regarde les monoides d'arbres comme nouvelle structure algebrique sur laquelle la theorie des automates d'arbres peut etre posee. Ceci amene a des techniques nouvelles et des resultats comme: la caracterisation de la regularite d'un langage d'arbres via la reconnaissabilite par les monoides finis (dont les varietes correspondent aux proprietes structurelles); un bon algorithme d'equivalence, la caracterisation de l'aperiodicite d'un langage d'arbres; une version non-restrictive de determinisme permettant l'extension des resultats classiques de determination et minimisation aux automates d'arbres descendants (racine-frontiere)

Cette thèse se situe à la frontière entre mathématiques et informatique théorique. Nous nous intéressons dans un premier temps aux automates finis et aux automates cellulaires. Bien qu’ils s’agissent de deux objets mathématiques assez différents, il est possible de les relier par des constructions explicites, en regardant la réalisation des suites automatiques dans les diagrammes espace-temps des automates cellulaires. Dans un second temps, nous étudions les corrélations discrètes de certaines suites automatiques, appelées suites généralisées de Rudin–Shapiro, qui se comportent comme des suites aléatoires pour la corrélation discrète d’ordre 2, bien qu’elles soient déterministes. Après une introduction des objets d’étude, que nous illustrons par plusieurs exemples, nous rappelons le résultat de Rowland et Yassawi, qui ont montré en 2015 qu’il était possible de construire de manière explicite toute suite p-automatique, dans le cas où p est un nombre premier, en colonne d’un automate cellulaire linéaire, à partir d’une configuration initiale finie. En utilisant leur méthode, nous obtenons différentes constructions de suites automatiques de référence, puis nous établissons un moyen explicite de construire toute une famille de suites p-automatiques, appelées suites généralisées de Rudin–Shapiro, que nous étudions dans la deuxième partie de la thèse, dans un cadre plus général. Nous nous intéressons également au cas de certaines suites non-automatiques, telles que l’indicatrice des polynômes et le mot de Fibonacci, que nous réussissons à construire en colonne d’automates cellulaires non-linéaires. Puis nous obtenons des résultats sur des recodages binaires, permettant de réduire le nombre de symboles dans les automates cellulaires. Grâce à un recodage binaire, nous avons également construit explicitement une suite 3-automatique sur un alphabet binaire, en colonne d’un automate cellulaire à 2 états, non-périodique à partir d’un certain rang, ce qui répond à une question posée par Rowland et Yassawi. Dans la deuxième partie de cette thèse, nous reprenons les travaux de Grant, Shallit et Stoll, qui ont établi en 2009 des résultats sur les corrélations discrètes de suites infinies sur des alphabets finis. En exploitant les propriétés de récursivité de la suite classique de Rudin–Shapiro, ils construisent une famille de suites déterministes sur des alphabets plus grands, pour lesquelles ils montrent que dans le cas où la taille de l’alphabet est sans facteur carré, la moyenne empirique des coefficients de corrélation d’ordre 2 a la même limite que dans le cas de suites où les lettres sont tirées aléatoirement, de manière uniforme et indépendamment. De plus, ils arrivent à quantifier explicitement le terme d’erreur. En généralisant leur construction à l’aide de la théorie des matrices de différence, nous arrivons à établir un résultat similaire pour des alphabets de taille quelconque ainsi qu’une amélioration du terme d’erreur dans certains cas. Tout comme Grant et al., nous nous servons de la théorie des sommes d’exponentielles pour démontrer notre résultat sur les corrélations discrètes d’ordre 2 de nos suites généralisées de Rudin–Shapiro. Dans la troisième partie, nous terminons par une approche combinatoire de ces questions, qui nous a permis d’obtenir une amélioration du terme d’erreur dans le cas où la taille de l’alphabet est un produit d’au moins deux nombres premiers distincts, et de généraliser certains de nos résultats
This thesis is at the interface between mathematics and theoretical computer science. In the first part, our main objects are finite automata and cellular automata. While relatively different in nature, it is possible to link both by explicit constructions. More specifically, it is possible to realise automatic sequences in the space-time diagrams of cellular automata. In the second part, we study discrete correlation properties of so-called generalised Rudin–Shapiro sequences. These are automatic sequences, hence deterministic, but show similar properties as random sequences with respect to their discrete correlation of order 2. After introducing the objects of study, illustrated by several examples, we first recall the result of Rowland and Yassawi. They showed in 2015 via an algebraic approach that it is possible to construct explicitly any p-automatic sequence (p is a prime number) as a column of a linear cellular automaton with a finite initial configuration. By using their method, we obtain several constructions of classical automatic sequences, and an explicit way to build a family of p-automatic sequences that we study in a more general context in the second part of the thesis. We also investigate several non-automatic sequences, such as the characteristic sequence of integer-valued polynomials and the Fibonacci word, which both can be realised as columns of non-linear cellular automata. We end this part by some results about binary recodings in order to reduce the number of symbols in the cellular automata. Under a binary recoding, we give explicitly a 3-automatic sequence on a binary alphabet, as a column of a cellular automaton with 2 states, that is not eventually periodic. This answers a question asked by Rowland et Yassawi. In the second part of the thesis, we take up research from 2009 of Grant, Shallit, and Stoll about discrete correlations of infinite sequences over finite alphabets. By using the recursivity properties of the classical Rudin–Shapiro sequence, they built a family of deterministic sequences over larger alpha- bets, called generalised Rudin–Shapiro sequences, for which they showed that when the size of the alphabet is squarefree, the empirical means of the discrete correlation coefficients of order 2 have the same limit as in the case of random sequences where each letter is independently and uniformly chosen. Moreover, they gave explicit error terms. We extend their construction by means of difference matrices and establish a similar result on alphabets of arbitrary size. On our way, we obtain an improvement of the error term in some cases. The methods stem, as those used by Grant et al., from the theory of exponential sums. In the third part, we use a more direct combinatorial approach to study correlations. This allows for an improvement of the error term when the size of the alphabet is a product of at least two distinct primes, and allows to generalise some of our results of the second part

La vérification de propriétés de sûreté des logiciels distribués basés sur des canaux fifo non bornés et fiables mène directement au model checking de systèmes infinis. Nous introduisons la famille des (q)ueueing (c)oncurrent (p)rocesses (QCP) composant des systèmes de transitions locaux, par exemple des automates finis/à pile, qui communiquent entre eux par des files fifo. Le problème d'atteignabilité des états de contrôle est indécidable pour des automates communicants et des automates à plusieurs piles, et par conséquent pour QCP.Nous présentons deux solutions pour contourner ce résultat négatif :Primo, une sur-approximation basée sur l'approche abstraire-tester-raffiner qui s'appuie sur notre nouveau concept de raffinement par chemin. Cette approche mène à permettre d'écrire un semi-algorithme du type CEGAR qui est implémenté avec des QDD et réalisé dans le framework McScM dont le banc d'essai conclut notre présentation.Secundo, nous proposons des restrictions pour les QCP à des piles locales pour démêler l'interaction causale entre les données locales (la pile), et la synchronisation globale. Nous montrons qu'en supposant qu'il existe une borne existentielle sur les exécutions et qu'en ajoutant une condition sur l'architecture, qui entrave la synchronisation de deux piles, on arrive à une réponse positive pour le problème de décidabilité de l'atteignabilité qui est EXPTime-complet (et qui généralise des résultats déjà connus). La construction de base repose sur une simulation du système par un automate à une pile équivalent du point de vue de l'atteignabilité --- sous-jacente, nos deux restrictions restreignent les exécutions à une forme hors-contexte. Nous montrons aussi que ces contraintes apparaissent souvent dans des situations ``concrètes''et qu'elles sont moins restrictives que celles actuellement connues. Une autre possibilité pour arriver à une solution pratiquement utilisable consiste à supposer une borne du problème de décidabilité : nous montrons que l'atteignabilité par un nombre borné de phases est décidable par un algorithme constructif qui est 2EXPTime-complet.Finalement, nous montrons qu'élargir les résultats positifs ci-dessus à la vérification de la logique linéaire temporelle demande soit de sacrifier l'expressivité de la logique soit d'ajouter des restrictions assez fortes aux QCP --- deux restrictions qui rendent cette approche inutilisable en pratique. En réutilisant notre argument de type ``hors-contexte'', nous représentons l'ordre partiel sous-jacent aux exécutions par des grammaires hypergraphes. Cela nous permet de bénéficier de résultats connus concertant le model checking des formules de la logique MSO sur les graphes (avec largeur arborescente bornée), et d'arriver aux premiers résultats concernant la vérification des propriétés sur l'ordre partiel des automates (à pile) communicants
The safety verification of distributed programs, that are based on reliable, unbounded fifo communication, leads in a straight line to model checking of infinite state systems. We introduce the family of (q)ueueing (c)oncurrent (p)rocesses (QCP): local transition systems, e.g., (pushdown-)automata, that are globally communicating over fifo channels. QCP inherits thus the known negative answers to the control-state reachability question from its members, above all from communicating automata and multi-stack pushdown systems. A feasible resolution of this question is, however, the corner stone for safety verification.We present two solutions to this intricacy: first, an over-approximation in the form of an abstract-check-refine algorithm on top of our novel notion of path invariant based refinement. This leads to a \cegar semi-algorithm that is implemented with the help of QDD and realized in a small software framework (McScM); the latter is benchmarked on a series ofsmall example protocols. Second, we propose restrictions for QCP with local pushdowns that untangle the causal interaction of local data, i.e., thestack, and global synchronization. We prove that an existential boundedness condition on runs together with an architectural restriction, that impedes the synchronization of two pushdowns, is sufficient and leads to an EXPTime-complete decision procedure (thus subsuming and generalizing known results). The underlying construction relies on a control-state reachability equivalent simulation on a single pushdown automaton, i.e., the context-freeness of the runs under the previous restrictions. We can demonstrate that our constraints arise ``naturally'' in certain classes of practical situations and are less restrictive than currently known ones. Another possibility to gain a practicable solution to safety verification involves limiting the decision question itself: we show that bounded phase reachability is decidable by a constructive algorithms in 2ExpTime, which is complete.Finally, trying to directly extend the previous positive results to model checking of linear temporal logic is not possible withouteither sacrificing expressivity or adding strong restrictions (i.e., that are not usable in practice). However, we can lift our context-freeness argument via hyperedge replacement grammars to graph-like representation of the partial order underlying each run of a QCP. Thus, we can directly apply the well-known results on MSO model checking on graphs (of bounded treewidth) to our setting and derive first results on verifying partial order properties on communicating (pushdown-) automata

Modéliser un système c'est lui trouver une représentation mathématique aussi fidèle que possible. Lorsque ce système est distribué (spatio-temporel), son modèle mathématique usuel est, depuis les années 60, un ensemble d'équations aux dérivées partielles. Depuis une décennie, les automates cellulaires (AC) se présentent comme de bons candidats pour décrire les systèmes distribués. De plus, leur mise en oeuvre est plus aisée. Dans ce travail, on montre que les automates cellulaires peuvent être utilisés pour décrire des systèmes dans le domaine des milieux déformables, tels que les déformations élastiques et thermoélastiques et le contact sans frottement. Les modèles d'automates cellulaires proposés permettent de simuler numériquement quelques propriétés génériques des phénomènes de déformation élastique-thermoélastique et le contact sans frottement tels que le déplacement des particules constituant le solide et l'énergie potentielle fournie. Ces modèles d'AC sont élaborés de telle sorte que la conservation de la masse et de la quantité de mouvement soit vérifiée. La mise en oeuvre de ces modèles est réalisée à l'aide d'un code Matlab
Modelling a distributed parameter systemis usually made by means of partial differential equations. Since the beginning of the 90's, cellular automata models represent a good candidate to describe spatio-temporal systems mainly formodellers who are not familiar with PDE's jargon. In this work, we show that cellular automata can be used to describe systems in the domain of solid deformation, such as deformation of elastic, thermoelastic and frictionless contact problems. The proposed cellular automata models are issued from generic properties of the deformation phenomena. They take into account conservation laws properties of theconsidered systems. Various applications and illustrative simulations have been developed with Matlab

Dans cette thèse, nous introduisons la théorie des graphes rationnels (qui sont reconnus par des transducteurs avec sorties étiquetées). Il s'agit de graphes étiquetés dont les sommets sont des mots dans un monoi͏̈de libre. Cette famille est une extension de nombreuses familles de graphes infinis connues à ce jour (les graphes context free de Muller et Schupp, les graphes équationnels de courcelle, les graphes préfixes-reconnaissables de Caucal ou encore les graphes automatiques de Sénizergues). Nous exhiberons certaines de leurs propriétés, telles que l'indécidabilité de nombreuses questions, ou bien des caractérisations interne et externe. Nous étudierons quelques unes de lerus sous-familles : les arbres rationnels, les graphes rationnels déterministes, ainsi que les graphes rationnels dont les sommets sont dans un monoi͏̈de commutatif. Enfin, nous nous intéresserons à leurs traces (à savoir l'ensemble des étiquettes des chemins partant d'un sommet pour arrivier à un sommet) et nous démontrerons que ces traces coi͏̈ncident avec les langages contextuels

Les transducteurs - automates avec sortie - et les relations rationnelles sont des concepts fondamentaux de la théorie des automates. Un rôle particulier est joué par la famille des fonctions rationnelles, en raison de ses propriétés remarquables et aujourd'hui classiques. Les relations de norme bornée sont une généralisation de celles-ci, introduite par Schützenberger en 1976, où le supremum des cardinalités des images est borné par une constante. Ces relations ont reçu une attention particulière en de differents travaux, dont le but a été de généraliser certaines propriétés des fonctions rationnelles; pourtant, les différences entre les techniques mises en oeuvre et la difficulté de quelques preuves conduisent à la nécessité d'une compréhension plus approfondie de ces propriétés. Cette thèse est consacrée à une présentation uniforme de quelques propriétés des relations de norme bornée, centrée sur la représentation de ces relations par des transducteurs et les manipulations de leur structure via des constructions de produits et de revêtements d'automates. Sont traités dans cette approche structurelle la décomposition d'une relation rationnelle de norme bornée dans une somme de fonctions rationnelles, résultat dont il est aussi donné une généralisation, la décidabilité de la famille des relations rationnelles de norme bornée, et la décidabilité de l'équivalence pour ces relations. Les constructions développées dans cette thèse permettent en particulier de nouvelles bornes de complexité, par rapport aux résultats connus
Transducers - automata with output - and rational relations are fundamental concepts in the field of automata theory. In particular, the rational functions are an important and well known family of relations due to the remarkable properties they possess. The bounded valued relations are a generalisation of the rational functions introduced by Schützenberger in 1976, where every image has a bounded number of elements. Even though some properties of the rational functions have been shown to hold in this more general setting, the use of techniques of distinct nature and the difficulty of some proofs indicate the need for a deeper understanding of these relations. This thesis brings a uniform presentation of some properties of the bounded valued rational relations, based on the representation by transducers and the manipulation of their structure with the use of produts and coverings of automata. Under this structural approach, it is tackled the decomposition of a bounded valued rational relation into a sum of rational functions and a generalisation, the decidability of the bounded valuedness and of the equivalence for the bounded valued transducers. The constructions developed in this thesis allow in particular clear algorithms with gains of complexity with respect to the known results

Nous considérons dans notre thèse la vérification des programmes ELECTRE et des systèmes à file réactifs embarqués(SFR Embarqués). Ces formalismes permettent la modélisation des systèmes réactifs avec mémorisation, ainsi que leur environnement. L'une des propriétés étudiées est la bornitude de la file de mémorisation, indispensable pour la correction des applications vérifiées. Nous prouvons l'indécidabilité de ce problème pour une classe très large de SFR Embarqués, et en conséquence, nous proposons une méthode de test pour ce problème. Nous prouvons par ailleurs que l'accessibilité est décidable pour les Lossy SFR Embarqués, une extension classique du modèle standard. Ce résultat nous permet d'envisager la vérification de propriétés de sûreté pour les SFR Embarqués : les propriétés satisfaites pour un Lossy SFR Embarqué le sont aussi par le SFR Embarqué correspondant. Puis, nous examinons la classe des applications temps-réel pour lesquelles nous proposons le modèle des SFR Hybrides Linéaires, obtenu depuis le modèle basique par l'ajout du temps qualitatif. Le problème de la bornitude étant indécidable, nous adaptons notre test à ce nouveau contexte. Finalement, même lorsque le modèle est borné, il est souvent trop gros pour pouvoir être vérifié en pratique. Nous introduisons donc une méthode de réduction, drastique lorsqu'elle s'applique, qui préserve la majorité des propriétés de logique temporelle
We are concern in our thesis by the verification of ELECTRE programs and Embedded Reactive Fiffo Systems (Embedded RFS). These two formalisms allow to model asynchronous reactive systems with event memorisation, along with their environment. Particularly, we focus on the boundedness problem which is seen as a correctness criterion for reactive systems. We prove that this problem is undeciable, thus we provide a testing method as a partial solution

La factorisation des mots infinis ou bi-infinis permet de caractériser les codes parmi les langages de mots finis. Elle permet aussi de classifier les codes selon le nombre de factorisations de certains types de mots infinis ou bi-infinis (les mots périodiques, par exemple), et de définir une notion de code pour mots finis et deux notions de code pour mots bi-infinis. Les diverses classes obtenues sont étudiées et comparées, dans le cas général et dans le cas rationnel. Les codes à délai de déchiffrage borné sont des codes pour mots infinis particuliers. De façon analogue, les codes à délai de synchronisation borné sont des codes pour mots bi-infinis. On étudie les propriétés des langages infinitaires engendrés par des codes à délai de déchiffrage borné et celles des langages bi-infinitaires engendrés par des codes à délai de synchronisation borné. Par exemple, on démontre que ces derniers sont des bilimites. On caractérise les codes à délai borné dans le cas rationnel. Finalement, on étudie les générateurs des langages bi-infinitaires. On montre, en particulier, que les codes très minces sont des générateurs minimaux. On montre aussi que l'on sait décider si la famille des générateurs d'un langage bi-infinitaire rationnel donné est vide ou non, et si elle contient un langage fini

Dans la première partie de ce manuscrit nous étudions les fonctions rationnelles, c'est-à-dire définies par des transducteurs unidirectionnels. Notre objectif est d'étendre aux transductions les nombreuses correspondances logique-algèbre qui ont été établies concernant les langages, notamment le célèbre théorème de Schützenberger-McNaughton-Papert. Dans le cadre des fonctions rationnelles sur les mots finis, nous obtenons une caractérisation à la Myhill-Nerode en termes de congruences d'indice fini. Cette caractérisation nous permet d'obtenir un résultat de transfert, à partir d'équivalences logique-algèbre pour les langages vers des équivalences pour les transductions. En particulier nous montrons comment décider si une fonction rationnelle est définissable en logique du premier ordre. Sur les mots infinis, nous pouvons également décider la définissabilité en logique du premier ordre, mais avec des résultats moins généraux.Les fonctions rationnelles sur les mots infinis sont plus difficiles à caractériser et nous obtenons un résultat plus faible: étant donné un transducteur nous montrons comment calculer un transducteur canonique, c'est-à-dire indépendant du transducteur initial, réalisant la même fonction.Cependant cette machine canonique nous permet tout de même de décider si une fonction est définissable en logique du premier ordre.Dans la seconde partie nous introduisons une logique pour les transductions et nous résolvons le problème de synthèse régulière: étant donnée une formule de la logique, peut-on obtenir un transducteur bidirectionnel déterministe satisfaisant la formule ?Dans la seconde partie nous considérons un problème de synthèse: étant donné une relation (spécification) peut-on obtenir une fonction (un programme) qui est inclus dans (qui satisfait) la relation. Les fonctions réalisées par des transducteurs bidirectionnels déterministes sont caractérisés par plusieurs modèles différents, y compris par les transducteurs MSO, et ont ainsi été nommées transductions régulières.Nous introduisons une logique expressive pour les transduction et nous résolvons le problème de synthèse régulière pour cette logique.Plus précisément nous fournissons un algorithme qui produit toujours une fonction régulière satisfaisant une spécification donnée en entrée.Nous exposons également un lien intéressant entre les transductions et les mots avec données.Par conséquent nous obtenons une logique expressive pour les mots avec données, pour laquelle le problème de satisfiabilité est décidable.
Option Informatique du Doctorat en Sciences
info:eu-repo/semantics/nonPublished

Les réseaux de transport multimodaux modernes sont essentiels pour la durabilité écologique et l’aisance économique des agglomérations urbaines, par conséquent aussi pour la qualité de vie de leurs habitants. D’ailleurs, le bon fonctionnement sur le plan de la compatibilité entre les différents services et lignes est essentiel pour leur acceptation, étant donné que (i) la plupart des trajets nécessitent des changements entre les lignes et que (ii) des investissements coûteux, dans le but de créer des liens plus directs avec la construction de nouvelles lignes ou l’extension de lignes existantes, ne sont pas à débattre. Une meilleure compréhension des interactions entre les modes et les lignes dans le contexte des transferts de passagers est ainsi d’une importance cruciale. Toutefois, comprendre ces transferts est singulièrement difficile dans le cas de situations inhabituelles comme des incidents de passagers et/ou si la demande dévie des plans statistiques à long terme. Ici le développement et l’intégration de modèles mathématiques sophistiqués peuvent remédier à ces inconvénients. À ce propos, la supervision via des modèles prévoyants représente un champ d’application très prometteur, analysée ici. La supervision selon des modèles prévoyants peut prendre différentes formes. Dans le présent travail, nous nous intéressons à l’analyse de l’impact basé sur des modèles de différentes actions, comme des départs en retard de certains véhicules après un arrêt, appliqué sur le fonctionnement du réseau de transport et sa gestion de situations de stress qui ne font pas partie des données statistiques. C’est pourquoi nous introduisons un nouveau modèle, un automate hybride avec une dynamique probabiliste, et nous montrons comment ce modèle profondément mathématique peut prédire le nombre de passagers dans et l’état de fonctionnement du véhicule en question du réseau de transport, d’abord par de simples estimations du nombre de tous les passagers et la connaissance exacte de l’état du véhicule au moment de l’incident. Ce nouvel automate réunit sous un même regard les passagers demandeurs de services de transport à parcours fixes ainsi que les véhicules capables de les assurer. Il prend en compte la capacité maximale et le fait que les passagers n’empruntent pas nécessairement des chemins efficaces, dont la représentation sous la forme d’une fonction de coût facilement compréhensible devient nécessaire. Chaque passager possède son propre profil de voyage qui définit un chemin fixe dans l’infrastructure du réseau de transport, et une préférence pour les différents services de transport sur son chemin. Les mouvements de véhicules sont inclus dans la dynamique du modèle, ce qui est essentiel pour l’analyse de l’impact de chaque action liée aux mouvements de véhicule. De surcroît, notre modèle prend en compte l’incertitude qui résulte du nombre inconnu de passagers au début et de passagers arrivant au fur et à mesure. Comparé aux modèles classiques d’automates hybrides, notre approche inspirée du style des réseaux de Pétri ne requiert pas le calcul de ces équations différentielles à la main. Ces systèmes peuvent être dérivés de la représentation essentiellement graphique d’une manière automatique pour le calcul en temps discret d’une prévision. Cette propriété de notre modèle réduit le risque de précisions faites par des humains et les erreurs qui en résulteraient. Après avoir introduit notre nouveau modèle, nous développons dans ce rapport également quelques éléments constitutifs sous la forme d'algorithmes qui visent les deux types d'impasses qui sont probables d'occurir pendant la simulation faisant un pronostic, c-à-d l'intégration numérique des systèmes de haute dimension d'équations différentielles et l'explosion combinatoire de son état discret. En plus, nous prouvons la faisabilité des calculs et nous montrons les bénéfices prospectifs de notre approche dans la forme de quelques tests simplistes et quelques cas plus réalistes
Without any doubt, modern multimodal transportation systems are vital to the ecological sustainability and the economic prosperity of urban agglomerations, and in doing so to the quality of life of their many inhabitants. Moreover it is known that a well-functioning interoperability of the different modes and lines in such networked systems is key to their acceptance given the fact that (i) many if not most trips between different origin/destination pairs require transfers, and (ii) costly infrastructure investments targeting the creation of more direct links through the construction of new or the extension of existing lines are not open to debate. Thus, a better understanding of how the different modes and lines in these systems interact through passenger transfers is of utmost importance. However, acquiring this understanding is particularly tricky in degraded situations where some or all transportation services cannot be provided as planned due to e.g. some passenger incident, and/or where the demand for these scheduled services deviates from any statistical long term-plannings. Here, the development for and integration of sophisticated mathematical models into the operation of such systems may provide remedy, where model-predictive supervision seems to be one very promising area of application which we consider here. Model-predictive supervision can take several forms. In this work, we focus on the model-based impact analysis of different actions, such as the delayed departure of some vehicle from a stop, applied to the operation of the considered transportation system upon some downgrading situation occurs which lacks statistical data. For this purpose, we introduce a new stochastic hybrid automaton model, and show how this mathematically profound model can be used to forecast the passenger numbers in and the vehicle operational state of this transportation system starting from estimations of all passenger numbers and an exact knowledge of the vehicle operational state at the time of the incident occurrence. Our new automaton model brings under the same roof, all passengers who demand fixed-route transportation services, and all vehicles which provide them. It explicitly accounts for all capacity-limits and the fact that passengers do not necessarily follow efficient paths which must be mapped to some simple to understand cost function. Instead, every passenger has a trip profile which defines a fixed route in the infrastructure of the transportation system, and a preference for the different transportation services along this route. Moreover, our model does not abstract away from all vehicle movements but explicitly includes them in its dynamics, which latter property is crucial to the impact analysis of any vehicle movement-related action. In addition our model accounts for uncertainty; resulting from unknown initial passenger numbers and unknown passenger arrival flows. Compared to classical modelling approaches for hybrid automata, our Petri net-styled approach does not require the end user to specify our model's many differential equations systems by hand. Instead, all these systems can be derived from the model's predominantly graphical specification in a fully automated manner for the discrete time computation of any forecast. This latter property of our model in turn reduces the risk of man-made specification and thus forecasting errors. Besides introducing our new model, we also develop in this report some algorithmic bricks which target two major bottlenecks which are likely to occur during its forecast-producing simulation, namely the numerical integration of the many high-dimensional systems of stochastic differential equations and the combinatorial explosion of its discrete state. Moreover, we proof the computational feasibility and show the prospective benefits of our approach in form of some simplistic test- and some more realistic use case

Dans cette thèse, nous nous intéressons à plusieurs notions d'invariants de l'évolution d'automates cellulaires dans le temps, en partant de la notion classique d'automate cellulaire conservateur. Nous présentons d'abord le modèle classique des automates cellulaires conservateurs, et plusieurs nouveaux résultats afférents. Puis nous introduisons les automates cellulaires décroissants, une extension naturelle des automates conservateurs, et montrons notamment que la décidabilité de cette propriété dépend de la dimension des automates considérés. Nous nous intéressons au rapport entre les automates décroissants et la notion de particule indifférenciée en introduisant les automates à particules. Enfin, nous étudions deux ensembles plus larges d'invariants, la conservation par fenêtre de fonctions de poids et les invariants d'évolution. Nous précisons la structure algébrique du premier modèle, et nous présentons nos premiers résultats concernant le deuxième.

Cette thèse s'intéresse dans un premier temps aux automates cellulaires réversibles, et dans un second temps aux tas de sable linéaires. Nous construisons diverses simulations reliant les automates cellulaires aux automates à partitions, en particulier celle des automates cellulaires réversibles par les automates à partitions réversibles, ce qui était une conjecture depuis 1990. Par des constructions successives, nous montrons que le ``Billiard ball model'' de Toffoli et Margolus est capable de simuler tous les automates à partitions réversibles de dimension 2. En rassemblant ces résultats, nous montrons qu'il existe des automates cellulaires réversibles capables de simuler tous les automates cellulaires réversibles de même dimension. Dans un espace linéaire, ``Tas de sable'' et ``Chip firing game'' sont équivalents. Nous portons notre attention sur le cas où les grains tombent un à un. Des motifs délimités par des signaux apparaissent au sein des configurations engendrées. Nous étudions la dynamique du système et démontrons un équivalent asymptotique. Nous étendons nos méthodes et nos résultats à d'autres types de configurations initiales. Dans chaque cas étudié, le temps parallèle est inférieur au temps séquentiel dans un rapport de l'ordre du nombre de piles mises en œuvre.

Reactive systems are computer systems that maintain continuous interaction with the environment in which they operate. Such systems are nowadays part of our daily life: think about common yet critical applications like engine control units in automotive, aircraft autopilots, medical aided- devices, or micro-controllers in mass production. Clearly, any flaw in such critical systems can have catastrophic consequences. However, they exhibit several characteristics, like resource limitation constraints, real-time responsiveness, concurrency that make them difficult to implement correctly. To ensure the design of reactive systems that are dependable, safe, and efficient, researchers and industrials have advocated the use of so-called formal methods, that rely on mathematical models to express precisely and analyze the behaviors of these systems.Automata theory provides a fundamental notion such as languages of program executions for which membership, emptiness, inclusion, and equivalence problems allow us to specify and verify properties of reactive systems. However, these Boolean notions yield the correctness of the system against a given property that sometimes, falls short of being satisfactory answers when the performances are prone to errors. As a consequence, a common engineering approach is not just to verify that a system satisfies a property, but whether it does so within a degree of quality and robustness.This thesis investigates the expressibility, recognition, and robustness of quantitative properties for program executions.• Firstly, we provide a survey on languages definable by regular automata with Presburger definable constraints on letter occurrences for which we provide descriptive complexity. Inspired by this model, we introduce an expression formalism that mixes formula and automata to define quantitative languages \ie function from words to integers. These expressions use Presburger arithmetic to combine values given by regular automata weighted by integers. We show that quantitative versions of the classical decision problems such as emptiness, universality, inclusion, and equivalence are computable. Then we investigate the extension of our expressions with a ''Kleene star'' style operator. This allows us to iterate an expression over smaller fragments of the input word, and to combine the results by taking their iterated sum. The decision problems quickly turn out to be not computable, but we introduce a new subclass based on a structural restriction for which algorithmic procedures exist.• Secondly, we consider a notion of robustness that places a distance on words, thus defining neighborhoods of program executions. A language is said to be robust if the membership satisfiability cannot differ for two ''close'' words, and that leads to robust versions of all the classical decision problems. Our contribution is to study robustness verification problems in the context of weighted transducers with different measures (sum, mean-payoff, and discounted sum). Here, the value associated by the transducer to rewrite a word into another denotes the cost of the noise that this rewriting induce. For each measure, we provide algorithms that determine whether a language is robust up to a given threshold of error and we solve the synthesis of the robust kernel for the sum measure. Furthermore, we provide case studies including modeling human control failures and approximate recognition of type-1 diabetes using robust detection of blood sugar level swings.• Finally, we observe that algorithms for structural patterns recognition of automata often share similar techniques. So, we introduce a generic logic to express structural properties of automata with outputs in some monoid, in particular, the set of predicates talking about the output values is parametric. Then, we consider three particular automata models (regular automata, transducers, and automata weighted by integers) and instantiate the generic logic for each of them. We give tight complexity results for the three logics with respect to the pattern recognition problem. We study the expressiveness of our logics by expressing classical structural patterns characterizing for instance unambiguity and polynomial ambiguity in the case of regular automata, determinizability, and finite-valuedness in the case of transducers and automata weighted by integers. As a consequence of our complexity results, we directly obtain that these classical properties can be decided in logarithmic space.
Doctorat en Sciences
info:eu-repo/semantics/nonPublished

Ce travail part de l'observation d'un resultat de p. Robba etabli en 1982 dont l'enonce est le suivant: si est un entier p-adique, alors la serie (1 + t) reduite modulo p est algebrique sur le corps des fractions rationnelles a coefficients dans le corps fini a p elements si et seulement si est rationnel. En remarquant que cette serie a une expression tres proche de celle d'un endomorphisme du groupe multiplicatif, on generalise ce resultat a une classe de groupes formels de lubin-tate dont le logarithme verifie une certaine condition d'algebricite. Nous interpretons ensuite ce resultat via le foncteur corps de normes de fontaine et wintenberger et en tirons des consequences sur l'independance algebrique des automorphismes de corps locaux. Dans la deuxieme partie de ce travail, nous etablissons l'analogue du theoreme de p. Robba dans le cas des modules de drinfeld de rang 1 definis sur le complete p-adique de l'anneau des polynomes a coefficients dans un corps fini avec p(t) irreductible unitaire de degre n et a coefficients dans ce meme corps fini.

Due to complex interactions between hardware mechanisms and software dynamic behaviours, achieving high performance independently from runtime or micro-architectural parameters is an extremely difficult task. As a solution, many scientific code sections are organized around optimized stand alone libraries that are either hand tuned or generated by an automatic tuning system targeting a single set of pre-defined codes. Performance is achieved at the cost of versatility. This thesis advocates an empirical approach for the automatic tuning of vector loops in most scientific applications. We detail the framework of an automated system taking place after high-level code transformation that resolves compiler code generation issues, and achieves high performance independently of many run-time parameters. Thus, it combines the high performance of libraries with the functionalities of compilers. The optimization process relies on the decomposition of critical vector loops into hierarchically organized code patterns. A systematic micro-benchmarking step is performed allowing to deduce optimizations techniques used to generate a new optimized vector loop stored in a database. Then, it is limited neither by the number of kernels nor to relying on a standardization of kernel calls and it avoids weak compiler low-level code generation. This framework was applied to the Alpha 21264, Power 4 and Itanium 2 processors and revealed performance behaviours due to complex interactions between hardware and software. Optimization techniques were deduced, applied to real-life codes and benchmarks and improved performance between 20% and 100% depending on the optimized code section
Des interactions complexes entre les mécanismes matériels et les comportements des logiciels à l'exécution rendent la tâche des compilateurs difficile pour obtenir de hautes performances, indépendamment du contexte ou de paramètres micro-architecturaux. Dans le cas du calcul scientifique, nombreux sont les codes organisés autour de fonctions standardisées afin d'utiliser des bibliothèques. Ces dernières peuvent être optimisées, de façon manuelle ou automatiquement mais que pour un seul ensemble de noyaux prédéfinis. La performance est alors obtenue au détriment de la flexibilité. Cette thèse défend une approche empirique de l'optimisation automatique de boucles vectorielles. Nous détaillons l'infrastructure d'un système automatique prenant place après des transformations de code haut-niveau et remplaçant la génération de code bas niveau des compilateurs parfois défaillante. Notre processus d'optimisation repose sur une décomposition des boucles vectorielles en des motifs de code organisés de façon hiérarchique dont les performances sont systématiquement évaluées et permettent de déduire des techniques d'optimisation servant à en générer des versions optimisées. Celles ci sont alors stockées dans une base de donnée. Il n'y a pas de limitation au nombre de noyaux à optimisés, et ne repose pas sur la génération de code bas niveau des compilateurs. Ce système appliqué sur plate-formes à base d'Alpha 21264, Power 4 et Itanium 2 a permis de révéler des performances complexes. Des optimisations ont néanmoins été déduites et appliquées sur des codes réels, améliorant les performances de 20% à 100% selon le code considéré

Ce travail étudie les déviations de sommes ergodiques pour des systèmes dynamiques substitutifs avec une matrice qui admet des valeurs propres de module supérieur à 1. Précisément, nous nous concentrons sur les substitutions telle que ces valeurs propres ne sont pas conjuguées. Dans un premier temps, on défini les lettres a-minimales et dominantes d'un mot pour étudier sa ligne brisée associé. On défini la ligne brisée normalisée et sa fonction limite. Pour l'étude des sommes ergodiques, on défini le sous-automate des lettres minimales. On donne des conditions sur une substitution de sorte qu'il y ait un nombre infini des sommes ergodiques égales à zéro pour un point x 2 X. Enfin, en utilisant un boucle dans une classe de Rauzy, on prouve l'existence d'un nombre infini d'échanges d'intervalles auto-similaires, dont la matrice de Rauzy a deux valeurs propres non conjuguées de module supérieur à 1. Et tout échange d'intervalles affine semi-conjugué à cet échange d'intervalles est aussi conjugué
This thesis focuses on the deviation of ergodic sums for a substitution dynamical systems with a matrix that admits eigenvalues of modulus larger than 1. Specifically, we concentrate on substitutions with non-conjugated eigenvalues. At first, we define the a-minimals letters and the dominant letters of a word to study its broken associated line. We define the normalize broken line and its limit function. For the study of ergodic sums, we define the sub-automaton of minimum letters. We give conditions on a substitution so that there is infinitely many zero sums ergodic for a point x 2 X. Finally, using a loop in a class of Rauzy, we prove the existence of infinitely many interval exchange transformation self-similar, whose Rauzy matrix has two non-conjugated eigenvalues larger than 1 and every affine interval exchange transformation that is semi-conjugated, is also conjugated

In this thesis, we consider three fundamental problems of transducers theory. The containment problem asks, given two transducers,whether the relation defined by the first is included into the relation defined by the second. The equivalence problem asks, given two transducers,whether they define the same relation. Finally, the sequential uniformisation problem,corresponding to the synthesis problem in the setting of transducers,asks, given a transducer, whether it is possible to deterministically pick an output correspondingto each input of its domain. These three decision problems are undecidable in general. As a first step, we consider different manners of recovering the decidability of the three problems considered.First, we characterise a family of classes of transducers, called controlled by effective languages, for which the containment and equivalence problems are decidable. Second, we add structural constraints to the problems considered: for instance, instead of only asking that two transducers define the same relation, we require that this relation is defined by both transducers in a similar way. This `similarity' is formalised through the notion of delay,used to measure the difference between the output production of two transducers. This allows us to introduce stronger decidable versions of our three decision problems, which we use to prove the decidability of the original problems in the setting of finite-valued transducers. In the second part, we study extensions of the automaton model,together with the adaptation of the sequential uniformisation problems to these new settings.Weighted automata are automata which,along each transition, output a weight in Z. Then, whereas a transducer preserves all the output mapped to a given input, weighted automata only preserve the maximal weight. In this setting, the sequential uniformisation problem turns into the determinisation problem: given a weighted automaton, is it possible to deterministically pick the maximal output mapped to each input? The decidability of this problem is open.The notion of delay allows us to devise a complete semi-algorithm deciding it. Finally, we consider two-way transducers, that are allowed to move back and forth over the input tape. These transducers enjoy good properties with respect to the sequential uniformisation problem: every transducer admits a sequential two-way uniformiser. We strengthen this result by showing that every transducer admits a reversible two-way uniformiser, i.e. a uniformiser that is both sequential and cosequential (backward sequential).
Doctorat en Sciences
info:eu-repo/semantics/nonPublished

Cette thèse est constituée de trois chapitres. Nous construisons des automorphismes de A[x, y] (où A est un anneau) à partir d'automorphismes à une indéterminée à coefficients dans un anneau quotient de A. Nous en déduisons plusieurs ap-plications : construction d'automorphismes de A[x, y] non-modérés, construction d'automorphismes de A[x, y] stablement modérés et de longueur de Berson infinie, théorème de transfert (permettant de constuire des variables en dimention impaire) et calcul d'une com-posante de l'adhérence de l'ensemble des automorphismes de k[x, y] de polydegré fixé. Nous élaborons une théorie automatique de la structure du groupe des automorphismes modérés de k[x, y, z]. Nous donnons un algo-rithme dont le but est d'obtenir des décompositions d'un automor-phisme modéré où le degré d'une composante croît. Nous appliquons cet algorithme pour obtenir des obstructions à la décomposition des z-automorphismes non-fortement modérés. Nous relions des propriétés de modération à l'exposant de Loja-siewicz d'une classe de polynômes de C[x, y, z].

Dans cette thèse, on se propose d'étudier les automates de Mealy, c'est-à-dire des transducteurs complets déterministes lettre à lettre ayant même alphabet d'entrée et de sortie. Ces automates sont utilisés depuis les années 60 pour engendrer des (semi-)groupes qui ont parfois des propriétés remarquables, permettant ainsi de résoudre plusieurs problèmes ouverts en théorie des (semi-)groupes. Dans ce travail, on s’intéresse plus particulièrement aux apports possibles de l'informatique théorique à l'étude de ces (semi-)groupes engendrés par automate. La thèse présentée s'articule autours de deux grands axes. Le premier, qui correspond aux chapitres II et III, traite des problèmes de décision et plus spécifiquement du problème de Burnside dans le chapitre II et des points singuliers dans le chapitre III. Dans ces deux chapitres on met en lien des propriétés structurelles de l'automate avec des propriétés du groupe engendré ou de son action. Le second axe, représenté par le chapitre IV, se rapporte à la génération aléatoire de groupes finis. On cherche, en tirant des automates de Mealy aléatoirement dans des classes spécifiques, à engendrer des groupes finis, et on aboutit à un résultat de convergence pour la distribution ainsi obtenue. Ce résultat fait écho au théorème de Dixon pour les groupes de permutations aléatoires
In this thesis, we study Mealy automata, i.e. complete, deterministic, letter-to-letter transducers which have same input and output alphabet. These automata have been used since the 60s to generate (semi)groups that sometimes have remarkable properties, that were used to solve several open problems in (semi)group theory. In this work, we focus more specifically on the possible contributions that theoretical computer science can bring to the study of these automaton (semi)groups.The thesis consists of two main axis. The first one, which corresponds to the Chapters II and III, deals with decision problems and more precisely with the Burnside problem in Chapter II and with singular points in Chapter III. In these two chapters, we link structural properties of the automaton with properties of the generated group or of its action. The second axis, which comprises the Chapter IV, is related with random generation of finite groups. We seek, by drawing random Mealy automata in specific classes, to generate finite groups, and obtain a convergence result for the obtained distribution. This result echoes Dixon's theorem on random permutation groups