Academic literature on the topic 'Automate mathématique'

Introduction. La théorie des automates finis fait partie de ce que l'on appelle aujourd'hui les mathématiques de l'informatique. Comme pour les autres spécialités de ce domaine, elle est née des travaux de logiciens et, pour les automates finis, c'est à Kleene que l'on doit le premier théorème. Cette théorie s'est considérablement développée depuis la période des fondations. La direction principale est l'étude des automates reconnaissant des suites finies ou mots. Elle présente des aspects mathématiques qui la rapprochent de domaines classiques comme par exemple la théorie combinatoire des groupes. Parallèlement, plusieurs auteurs ont étudié le comportement des automates finis sur des objets plus généraux que les mots. C'est le cas notamment pour la théorie des automates reconnaissant des arbres. C'est aussi le cas pour les automates reconnaissant des mots infinis qui sont le sujet de cet article.

En vue d'une densification urbaine durable, un outil ayant pour but d'évaluer et d'assister la conception d'îlots urbains compacts pourvus d'une densité de population cible a été créé et testé dans le cadre du projet CoMod. Le concept de compacité spatiale est appliqué ici, à l'échelle architecturale, sur le bâti, le non-bâti et les deux combinés. Cette approche encourage les typo-morphologies économes en terrain et en ressources matérielles tout en étant efficaces d'un point de vue énergétique. Afin d'éviter une potentielle exagération de ce concept divers critères notamment relatifs aux espaces verts, aux ombres ainsi que des distances et surfaces minimales sont considérés. Cependant, viser la compacité urbaine rencontre une conciliation difficile entre les divers critères quantitatifs et qualitatifs. De nombreux outils mathématiques ont déjà été appliqués à des problems urbanistiques (méthodes d'optimisation, aide à la décision, automates cellulaires, ensembles fractals, etc.). L'étude de typo-morphologies compactes avec l'aide de la théorie des jeux ou de la recherche locale peut aider à la gestion des problèmes provenant de critères conflictuels. Dans cet article nous présentons un prototype de programme qui génère des îlots urbains en utilisant la recherche locale et la théorie des jeux.

Janello Torriani, also known by his Spanish name Juanelo Turriano (Cremona ca. 1500–Toledo 1585), was a blacksmith, locksmith, constructor of scientific instruments, famous inventor of mechanical devices, automata-maker, clockmaker to Emperor Charles V, hydraulic engineer, mathematician, star-gazer, bell-designer, surveyor, and author of mathematical treatises to King Philip II of Spain. He was especially famous for his amazing planetary clocks, which he both designed and physically crafted (thanks to the invention of the first known machine-tool to cut gears), and for his hydraulic device of Toledo, the first giant machine in history that elevated water over a slope of ninety metres a distance of three hundred meters. Given this multifaceted professional profile, Torriani has been considered a Renaissance polymath and a genius. This article goes beyond the anachronistic understanding of these two categories, which it deconstructs, by analyzing Torriani’s education and the context of the mathematical professions during the sixteenth century. Janello Torriani, aussi connu sous le nom espagnol de Juanelo Turriano (Crémone c. 1500 – Tolède 1585) fut d’abord au service de l’empereur Charles Quint comme forgeron, serrurier, facteur d’instruments scientifiques, inventeur célèbre pour ses dispositifs mécaniques, constructeur d’automates et horloger ; au service du roi Philippe II d’Espagne, il fut ingénieur hydraulique, mathématicien, astronome, concepteur de cloches, arpenteur géomètre et auteur de traités de mathématiques. Il est surtout connu pour ses étonnantes horloges astronomiques qu’il a à la fois conçues et construites (grâce à l’invention des premières machines à couper les engrenages), et pour ses dispositifs hydrauliques de Tolède, dont la toute première machine permettant d’amener de l’eau vers le haut d’une pente sur une distance de 300 mètres. Pour ses multiples compétences professionnelles, Torriani est considéré comme un véritable polymathe et un génie de la Renaissance. Cet article cherche à dépasser une compréhension anachronique de ces deux catégories, qu’il pour déconstruit, en analysant la formation de Torriani et le contexte de la profession de mathématicien au XVIe siècle.

International audience The $\textit{parallel chip-firing game}$ is an automaton on graphs in which vertices "fire'' chips to their neighbors. This simple model, analogous to sandpiles forming and collapsing, contains much emergent complexity and has connections to different areas of mathematics including self-organized criticality and the study of the sandpile group. In this work, we study $\textit{firing sequences}$, which describe each vertex's interaction with its neighbors in this game. Our main contribution is a complete characterization of the periodic firing sequences that can occur in a game, which have a surprisingly simple combinatorial description. We also obtain other results about local behavior of the game after introducing the concept of $\textit{motors}$. Le $\textit{parallel chip-firing game}$, c’est une automate sur les graphiques, dans lequel les sommets “tirent” des jetons à leurs voisins. Ce modèle simple, semblable aux tas de sable qui forment et s’affaissent, contient beaucoup de complexité émergente et a des connections avec différents domaines de mathématiques, incluant le $\textit{self-organized criticality}$ et l’étude du $\textit{sandpile group}$. Dans ce projet, on étudie les $\textit{firing sequences}$, qui décrivent les interactions de chaque sommet avec ses voisins dans le jeu. Notre contribution principale est une caractérisation complète des séquences de tir qui peuvent arriver dans une jeu, qui ont une description combinatoire assez simple. Nous obtenonsaussi d'autres résultats sur le conduite locale du jeu après l’introduction du concept des $\textit{motors}$.

The author discusses the media developed to record and process sunlight as an environmental threat, especially ozone holes, ultraviolet indexes, and automated hazard alerts. These media are illustrative of how environmental precaution is produced by Earthobserving systems and indicative of how the politics of industrial transformations are shaped by the logistics of maintaining a data-processing infrastructure for observing dangerous environmental changes. The article attempts to process the effects of the shifting technological dimensions of Earth-observing with respect to the mathematical models and media infrastructure required for processing signals of environmental change, and to re-situate how we understand precaution on this terrain.L’auteur discute des médias développés pour enregistrer et évaluer la lumière du soleil en tant que menace pour l’environnement, surtout en ce qui a trait aux trous dans l’ozone, aux index de lumière ultraviolette et aux avertissements de danger automatisés. Ces médias illustrent comment les systèmes qui observent la Terre sont à la source de précautions environnementales. Ils indiquent aussi comment les politiques sur les transformations industrielles sont formulées à partir de la logistique requise pour le maintien d’une infrastructure de traitement de données sur l’observation de changements environnementaux dangereux. Cet article tente d’évaluer les effets des dimensions technologiques fluctuantes de l’observation de la Terre par rapport aux modèles mathématiques et à l’infrastructure médiatique nécessaires pour traiter les indices de changements environnementaux. It tente en outre de resituer comment nous envisageons la précaution dans de telles circonstances.

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.