To see the other types of publications on this topic, follow the link: Théorie algébgrique des automates.
Dissertations / Theses on the topic 'Théorie algébgrique des automates'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Théorie algébgrique des automates.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Soyez-Martin, Claire. "From semigroup theory to vectorization : recognizing regular languages." Electronic Thesis or Diss., Université de Lille (2022-....), 2023. http://www.theses.fr/2023ULILB052.
Full textAbstract:
L'évaluation efficace des expressions régulières constitue un défi persistant depuis de nombreuses décennies. Au fil du temps, des progrès substantiels ont été réalisés grâce à une variété d'approches, allant de nouveaux et ingénieux algorithmes à des optimisations complexes de bas niveau.Les outils de pointe de ce domaine utilisent ces techniques d'optimisation, et repoussent constamment les limites de leur efficacité. Une avancée notoire réside dans l'intégration de la vectorisation, qui exploite une forme de parallélisme de bas niveau pour traiter l'entrée par blocs, entraînant ainsi d'importantes améliorations de performances. Malgré une recherche approfondie sur la conception d'algorithmes sur mesure pour des tâches particulières, ces solutions manquent souvent de généralisabilité, car la méthodologie sous-jacente à ces algorithmes ne peut pas être appliquée de manière indiscriminée à n'importe quelle expression régulière, ce qui rend difficile son intégration dans les outils existants.Cette thèse présente un cadre théorique permettant de générer des programmes vectorisés particuliers capables d'évaluer les expressions régulières correspondant aux expressions rationnelles appartenant à une classe logique donnée. L'intérêt de ces programmes vectorisés vient de l'utilisation de la théorie algébrique des automates, qui offre certains outils algébriques permettant de traiter les lettres en parallèle. Ces outils permettent également d'analyser les langages réguliers plus finement, offrent accès à des optimisations des programmes vectorisés basées sur les propriétés algébriques de ces langages. Cette thèse apporte des contributions dans deux domaines. D'une part, nous présentons des implémentations et des benchmarks préliminaires, afin d'étudier les possibilités offertes par l'utilisation de l'algèbre et de la vectorisation dans les algorithmes d'évaluation des expressions régulières. D'autre part, nous proposons des algorithmes capables de générer des programmes vectorisés reconnaissant les langages appartenant à deux classes d'expressions rationnelles, la logique du premier ordre et sa restriction aux formules utilisant au plus deux variablesThe pursuit of optimizing regular expression validation has been a long-standing challenge,spanning several decades. Over time, substantial progress has been made through a vast range of approaches, spanning from ingenious new algorithms to intricate low-level optimizations.Cutting-edge tools have harnessed these optimization techniques to continually push the boundaries of efficient execution. One notable advancement is the integration of vectorization, a method that leverage low-level parallelism to process data in batches, resulting in significant performance enhancements. While there has been extensive research on designing handmade tailored algorithms for particular languages, these solutions often lack generalizability, as the underlying methodology cannot be applied indiscriminately to any regular expression, which makes it difficult to integrate to existing tools.This thesis provides a theoretical framework in which it is possible to generate vectorized programs for regular expressions corresponding to rational expressions in a given class. To do so, we rely on the algebraic theory of automata, which provides tools to process letters in parallel. These tools also allow for a deeper understanding of the underlying regular language, which gives access to some properties that are useful when producing vectorized algorithms. The contribution of this thesis is twofold. First, it provides implementations and preliminary benchmarks to study the potential efficiency of algorithms using algebra and vectorization. Second, it gives algorithms that construct vectorized programs for languages in specific classes of rational expressions, namely the first order logic and its subset restricted to two variables
2
Hélouët, Loïc. "Automates d'ordres : théorie et applications." Habilitation à diriger des recherches, Université Rennes 1, 2013. http://tel.archives-ouvertes.fr/tel-00926742.
Full textAbstract:
Les automates d'ordres, plus connus sous le nom de Message sequence Charts (MSC), ont connu une énorme popularité depuis les années 1990. Ce succès est à la fois académique et industriel. Les raisons de ce succès sont multiples : le modèle est simple et s'apprend très vite. De plus il possède une puissance d'expression supérieure à celle des automates finis, et pose des problèmes difficiles. L'apparente simplicité des MSCs est en fait trompeuse, et de nombreuses manipulations algorithmiques se révèlent rapidement être des problèmes indécidables. Dans ce document, nous revenons sur 10 années de recherches sur les Message Sequence Charts, et plus généralement sur les langages de scénarios, et tirons quelques conclusions à partir des travaux effectués. Nous revenons sur les propriétés formelles des Message Sequence charts, leur décidabilité, et les sous-classes du langage permettant la décision de tel ou tel problème. L'approche classique pour traiter un problème sur les MSCs est de trouver la plus grande classe possible sur laquelle ce problème est décidable. Un autre challenge est d'augmenter la puissance d'expression des MSCs sans perdre en décidabilité. Nous proposons plusieurs extensions de ce type, permettant la crétion dynamique de processus, ou la définition de protocoles de type "fenêtre glissante". Comme tout modèle formel, les MSCs peuvent difficilement dépasser une taille critique au delà de laquelle un utilisateur ne peut plus vraiment comprendre le diagramme qu'il a sous les yeux. Pour pallier à cette limite, une solution est de travailler sur de plus petits modules comportementaux, puis de les assembler pour obtenir des ensembles de comportements plus grands. Nous étudions plusieurs mécanismes permettant de composer des MSCs, et sur la robustesses des sous-classes de scénarios connues à la composition. La conclusion ce cette partie est assez négative: les scénarios se composent difficilement, et lorsqu'une composition est faisable, peu de propriétés des modèles composés sont préservées. Nous apportons ensuite une contributions à la synthèse automatique de programmes distribués à partir de spécification données sous forme d'automates d'ordres. Cette question répond à un besoin pratique, et permet de situer un role possible des scénarios dans des processus de conception de logiciels distribués. Nous montrons que la synthèse automatique est possible sur un sous ensemble raisonnable des automates d'ordres. Dans une seconde partie de ce document, nous étudions des applications possibles pour les MSCs. Nous regardons entre autres des algorithmes de model-checking, permettant de découvrir des erreurs au moment de la spécification d'un système distribué par des MSCs. La seconde application considérée est le diagnostic, qui permet d'expliciter à l'aide d'un modèle les comportement d'un système réel instrumenté. Enfin, nous regardons l'utilisation des MSCs pour la recherche de failles de sécurité dans un système. Ces deux applications montrent des domaines réalistes d'utilisation des scénarios. Pour finir, nous tirons quelques conclusions sur les scénarios au regard du contenu du document et du travail de ces 10 dernières années. Nous proposons ensuite quelques perspectives de recherche.
3
Broglio, Annie. "Prédiction par automates." Aix-Marseille 1, 1991. http://www.theses.fr/1991AIX11385.
Full textAbstract:
Nous introduisons une notion de prediction pour des suites infinies sur un alphabet a q elements. Nous lisons a l'aide d'un automate une suite, lettre a lettre puis precisions a chaque etape une lettre que nous comparons a la lettre suivante de la suite. Nous calculons alors un rapport de bonne prediction. Les suites normales (c'est-a-dire completement aleatoires) sont celles ayant un rapport 1/q. Les sous-suites obtenues a l'aide d'un automate ont le meme ensemble de rapports de prediction que les suites dont elles sont extraites. Nous construisons de bons predicteurs pour certaines suites de faible complexite
4
Podelski, Andreas. "Monoïdes d'arbres et automates d'arbres." Paris 7, 1989. http://www.theses.fr/1989PA077247.
Full textAbstract:
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)
5
Mosconi, Jean. "La constitution de la théorie des automates." Paris 1, 1989. http://www.theses.fr/1989PA010611.
Full textAbstract:
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 notammentIn 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
6
Dartois, Luc. "Méthodes algébriques pour la théorie des automates." Paris 7, 2014. http://www.theses.fr/2014PA077236.
Full textAbstract:
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 nouveauxIn 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
7
Samuelides, Mathias. "Automates d'arbres à jetons." Phd thesis, Université Paris-Diderot - Paris VII, 2007. http://tel.archives-ouvertes.fr/tel-00255024.
Full textAbstract:
Le sujet porte sur l'étude de deux modèles d'automates à jetons sur des arbres binaires finis étiquetés par un alphabet fini. Ces automates séquentiels se déplacent le long des arêtes et peuvent utiliser un nombre fixé de jetons pour se repérer dans un arbre. Une discipline de pile est imposé au placement des jetons, de plus, dans le modèle fort un jeton peut être levé à distance alors que dans le modèle faible un jeton peut être levé uniquement s'il est posé sur le n\oe ud courant. Les automates cheminants correspondent au cas des automates d'arbres à 0 jeton. L'étude des automates d'arbres à jetons est motivée par la caractérisation du pouvoir d'expression et de la complexité du langage de requêtes XPATH qui permet de sélectionner des éléments et de définir des chemins dans des documents XML et qui est le noyau de langages de transformation de documents XML tels que XSLT.Une première contribution a été de prouver que les variantes déterministes des deux modèles d'automates d'arbres à jetons sont fermées par complément. Nous donnons alors une nouvelle présentation de la preuve de la caractérisation du modèle fort des automates d'arbres à jetons qui a été établie par Engelfriet et Hoogeboom.
Une autre contribution a été de montrer que les deux modèles d'automates à jetons sont équivalents, que le pouvoir d'expression des automates d'arbres à jetons augmente avec le nombre de jetons et qu'il n'est pas toujours possible de déterminiser un automate d'arbres cheminant même si on s'autorise à ajouter un nombre fixé de jetons.
Une dernière contribution a été de prouver que les problèmes du vide et de l'inclusion sont n-EXPTIME complets pour les classes d'automates à n jetons avec n supérieur à 1.
8
Oaurdi, Faissal. "Expressions rationnelles et automates réduits." Rouen, 2007. http://www.theses.fr/2007ROUES006.
Full textAbstract:
Le thème général de cette thèse s’inscrit dans le cadre de la théorie des automates et s’articule autour de la conception des algorithmes efficaces pour le problème de conversion d’expressions rationnelles avec ou sans multiplicités en des automates ayant une taille réduite. Nous étudions différents types d’automates réduits définis à partir d’une expression rationnelle : l’automate des positions, l’automate des c-continuations, l’automate des équations et l’automate des ensembles follows communs. Nous donnons une comparaison entre l’automate des follows et l’automate des équations, d’une part, et d’autre part nous proposons un algorithme efficace pour la construction de ce dernier, basé sur la minimisation d’automate acyclique. Nous nous intéressons ensuite à la généralisation de ces automates et leurs constructions au cas des multiplicités. Nous développons deux nouveaux algorithmes quadratiques pour le problème de conversion dans le cas des multiplicités. Le premier, basé sur la structure ZPC étendu, permet la construction de l’automate de positions à multiplicités. Le deuxième, basé sur les c-continuations, construit l’automate des équations à multiplicités. Nous définissons une extension au cas de multiplicité de l’automate des ensembles follows communs introduits par Hromckovic et al. En 1997. Nous montrons ensuite que cet automate peut être obtenu en temps O(nlog2(n)) où n est la taille de l’expression de départThe general topic of this thesis lies within the scope of the automata theory and turns on the design of efficient algorithms for the problem of conversion of weighted and boolean regular expressions into finite automata having small sizes. We study various types of reduced automata defined from regular expressions : the position automaton, the follow automaton, the c-continuation automaton and the common follows automaton. On the one hand, we give a comparison between the follow automaton and the equation automaton. On the other hand, we describe a new efficient algorithm based on the minimization of an acyclic automaton, for the construction of the equation automaton. We were also interested in the generalization of these automata and their constructions for the weighted regular expressions. We generalize the notion of ZPC structure for the weighted case. We develop two new quadratic algorithms for the problem of the conversion of weighted regular expressions. The first algorithm is based on the extended ZPC structure, allows the construction of the position automaton with multiplicities. The second one, based on the c-continuations, computes the equation automaton with multiplicities. We finally define an extension to the weighted case of the common follows set automaton introduced by Hromckovic et al. We show that this automaton can be obtained in O(nlog2(n)) time where n is the size of the weighted regular expressions
9
Loraud, Nathalie. "Numérations généralisées, langages et automates." Aix-Marseille 1, 1996. http://www.theses.fr/1996AIX11019.
Full textAbstract:
Les systemes de numeration standards (i. E. Obtenus par l'algorithme glouton) sont examines du point de vue de la reconnaissabilite de leur langage. Une relation entre systemes de numeration dans une base etoile-recurrente et beta-shifts est etablie, ce qui complete un resultat d'anne bertrand-mathis. La caracterisation de bases de numeration donnant un langage regulier est obtenue pour certaines familles d'echelles (suites arithmetico-geometriques, bases de cantor, d'ostrowski,). D'autre part, les notions d'opacite et d'opacite restreinte d'un automate fini (introduites par michel mendes france) sont approfondies. La conjecture d'egalite est demontree dans le cadre classique (grace, entre autre, a la fonction de yao) ; dans le cadre symbolique, une famille de contre-exemples est proposee
10
Verma, Kumar Neeraj. "Automates d'arbres bidirectionnels modulo théories équationnelles." Cachan, Ecole normale supérieure, 2003. http://www.theses.fr/2003DENS0027.
Full text
11
Chemlal, Rezki. "Valeurs propres des automates cellulaires." Phd thesis, Université Paris-Est, 2012. http://tel.archives-ouvertes.fr/tel-00794398.
Full textAbstract:
On s'intéresse dans ce travail aux automates cellulaires unidimensionnels qui ont été largement étudiés mais où il reste beaucoup à faire. La théorie spectrale des automates cellulaires a notamment été peu abordée à l'exception de quelques résultats indirects. On cherche a mieux comprendre les cadres topologiques et ergodiques en étudiant l'existence de valeurs propres en particulier celles irrationnelles c'est à dire de la forme e^{2Iπα} où α est un irrationnel et I la racine carrée de l'unité. Cette question ne semble pas avoir été abordée jusqu'à présent. Dans le cadre topologique les résultats sur l'équicontinuité de Kůrka et Blanchard et Tisseur permettent de déduire directement que tout automate cellulaire équicontinu possède des valeurs propres topologiques rationnelles. La densité des points périodiques pour le décalage empêche l'existence de valeurs propres topologiques irrationnelles. La densité des points périodiques pour l'automate cellulaire semble être liée à la question des valeurs propres. Dans le cadre topologique, si l'automate cellulaire possède des points d'équicontinuité sans être équicontinu, la densité des points périodiques a comme conséquence le fait que le spectre représente l'ensemble des racines rationnelles de l'unité c'est à dire tous les nombres de la forme e^{2Iπα} avec α∈Q .Dans le cadre mesuré, la question devient plus difficile, on s'intéresse à la dynamique des automates cellulaires surjectifs pour lesquels la mesure uniforme est invariante en vertu du théorème de Hedlund. La plupart des résultats obtenus demeurent valable dans un cadre plus large. Nous commençons par montrer que les automates cellulaires ayant des points d'équicontinuité ne possèdent pas de valeurs propres mesurables irrationnelles. Ce résultat se généralise aux automates cellulaires possédant des points μ-équicontinu selon la définition de Gilman. Nous démontrons finalement que les automates cellulaires possédant des points μ-équicontinu selon la définition de Gilman possèdent des valeurs propres rationnelles
12
Provillard, Julien. "Automates cellulaires non-uniformes." Nice, 2012. http://www.theses.fr/2012NICE4082.
Full textAbstract:
Les automates cellulaires (CA) sont des systèmes dynamiques discrets très utilisés dans de nombreux domaines scientifiques. Leurs principales caractéristiques sont d’agir de manière locale, synchrone et uniforme sur l’ensemble des cellules d’une grille régulière. Ces systèmes produisent une grande variété de dynamiques et ont été largement étudiés dans la littérature. De nombreuses variantes ont été proposées. Dans ce travail de thèse nous nous intéresserons aux automates cellulaires non-uniformes (nu-CA). Il s’agit, essentiellement, d’automates cellulaires dans lesquels la contrainte d’uniformité a été relâchée. Dans un premier temps, nous considérerons une famille de nu-CA qui permet de représenter des perturbations dans la structure d’un CA. Il s’agit d’étudier l’influence d’une panne ou d’une erreur ponctuelle dans l’implémentation d’un CA et notamment son influence sur la dynamique. Nous verrons que de nombreuses propriétés ne sont pas stables (à l’exception notable de l’équicontinuité) mais que l’on peut alors établir des liens entre un CA et ses modèles de perturbation. Dans une seconde partie, nous cherchons à déterminer les propriétés que peut avoir un nu6CA en fonction des comportements locaux que l’on peut observer. On se donne un ensemble de règles locales qui peuvent intervenir dans un nu-CA et nous nous intéressons à la façon d’agencer ces règles pour produire certaines propriétés dans l’automate induit. Nous associons alors, à chacune de ces propriétés, un langage de distributions que nous caractérisons) à l’aide de la théorie des langagesCellular automata (CA) are discrete dynamical systems widely used in many scientific domains. Their main characteristic is to act locally, synchronously and uniformly on a regular set of elementary components called cells. These systems have a huge variety of dynamical behaviours and have been extensively studied in literature. Several variants have been proposed. In this work we are interested in non-uniform cellular automata (nu-CA). They are, essentially, CA in which the uniformity constraint has been relaxed. In the first part, we study a family of nu6CZA which allows to easily representing perturbations of the structure of a CA. The idea is to study the impact of the dynamics of failure or of an error in the physical implementation of a CA by electronic components. Indeed, we will prove that several dynamical properties are not structurally stable (except for the equicontinuity property). However, we will show how to link properties of a CA and its “perturbed” versions. In the second part, we try to infer the global properties of a nu-CA from the local behaviours we can observe. Given a set of local rules which can appear in a given nu-CA, we study the way of mowing them to obtain given global behaviours. Moreover, we associate global properties with peculiar formal languages and we completely characterize these formal languages. In this way we obtain a natural notion of complexity for properties on nu-CA. A property is a complex as the class of languages from which it is characterizes
13
Roux, Bernard. "Une approche relationnelle des automates et de l'ordonnancement." Lyon 1, 2000. http://www.theses.fr/2000LYO10255.
Full text
14
Carayol, Arnaud. "Automates infinis, logique et langages." Rennes 1, 2006. https://tel.archives-ouvertes.fr/tel-00628513.
Full textAbstract:
Cette thèse s'inscrit dans l'étude des graphes infinis de présentation finie. Nous nous intéressons à la fois à leurs propriétés logiques et aux langages qui leur sont associés. Nous nous concentrons sur l'étude des graphes infinis associés aux automates à pile d'ordre supérieur. Notre première contribution est la définition d'une notion de rationalité pour les piles d'ordre supérieur. Nous montrons que cette notion partage de nombreuses propriétés de la rationalité sur les mots : clôture par complémentaire, accepteurs déterministes et complets, et caractérisation en logique du second ordre monadique. Nous établissons un lien étroit entre les automates à pile d'ordre supérieur et les ensembles rationnels de piles d'ordre supérieur. Notre seconde contribution est l'étude structurelle des graphes associés à ces automates. Nous en donnons différentes caractérisations qui montrent la robustesse de ces familles de graphes infinis.
15
Reimen, Nicolas. "Contribution à l'étude des automates cellulaires." Paris 7, 1993. http://www.theses.fr/1993PA077335.
Full textAbstract:
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
16
Roka, Zsuzsanna. "Automates cellulaires sur graphes de Cayley." Lyon 1, 1994. http://www.theses.fr/1994LYO10180.
Full textAbstract:
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
17
Lombardy, Sylvain. "Approche structurelle de quelques problèmes de la théorie des automates." Phd thesis, Ecole nationale supérieure des telecommunications - ENST, 2001. http://tel.archives-ouvertes.fr/tel-00737830.
Full textAbstract:
Les travaux développés dans cette thèse empruntent trois directions principales. D'une part, une étude attentive des propriétés de l'automate universel d'un langage rationnel a été menée. Cet automate fini (introduit sous une forme sensiblement différente par J.H. Conway) accepte le langage et a la particularité de contenir l'image par morphisme de n'importe quel automate équivalent. Nous donnons un algorithme pour le construire à partir de l'automate minimal. L'exploitation des propriétés de l'automate universel d'un langage réversible nous a permis de montrer qu'il existe un sous-automate quasi-réversible (à partir duquel on peut facilement construire un automate réversible) de l'automate universel équivalent. De plus, il existe un tel sous-automate sur lequel on peut calculer une expression rationnelle qui représente le langageavec une hauteur d'étoile minimale. D'autre part, nous donnons un algorithme pour décider la séquentialité d'une série (max,+) ou (min,+) réalisée par par un automate sur un alphabet à une lettre. La complexité de cet algorithme ne dépend que de la structure de l'automate et non des valeurs des coefficients. Nous présentons aussi un algorithme qui permet de procéder directement à la déterminisation d'un automate réalisant une série séquentielle et, si ce n'est pas le cas, à l'obtention d'un automate équivalent non ambigu. Ce dernier point rejoint le résultat de Stéphane Gaubert qui montre qu'on peut obtenir une expression (et donc un automate) non ambiguë pour n'importe quel série (max,+) rationnelle sur une lettre. Enfin, nous proposons un algorithme pour construire, à partir d'une expression rationnelle avec multiplicité, un automate qui représente la même série. Cet algorithme, qui est la généralisation des travaux d'Antimirov, permet d'obtenir explicitement un ensemble fini d'expressions qui représentent un ensemble générateur du semi-module auquel appartiennent les quotients de la série rationnelle.
18
Caron, Pascal. "Langages rationnels et automates : de la théorie à la programmation." Rouen, 1997. http://www.theses.fr/1997ROUES079.
Full textAbstract:
Cette thèse constitue un point de départ pour la programmation d'un système de calcul formel sur les automates, les semigroupes et les langages rationnels. On y trouve la caractérisation des automates construits selon l'algorithme de Glushkov. Des caractérisations de familles de langages testables à partir de leurs automates minimaux y sont également décrites. Le logiciel AGL regroupe un ensemble de packages Maple sur les automates, les semigroupes et les langages rationnels. L'ensemble des algorithmes déduits des caractérisations y est implémenté. Ce logiciel constitue un prototype pour un système de calcul formel dédié aux automates, aux semigroupes et aux langages rationnels.
19
Dahmoune, Mohamed. "Quelques contributions en logique mathématique et en théorie des automates." Thesis, Paris Est, 2014. http://www.theses.fr/2014PEST1013/document.
Full textAbstract:
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 à trousThis 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
20
Carayol, Arnaud. "Automates infinis, logiques et langages." Phd thesis, Université Rennes 1, 2006. http://tel.archives-ouvertes.fr/tel-00628513.
Full textAbstract:
Cette thèse s'inscrit dans l'étude des graphes infinis de présentation finie. Nous nous intéressons à la fois à leurs propriétés logiques et aux langages qui leur sont associés. Nous nous concentrons sur l'étude des graphes infinis associés aux automates à pile d'ordre supérieur. Notre première contribution est la définition d'une notion de rationalité pour les piles d'ordre supérieur. Nous montrons que cette notion partage de nombreuses propriétés de la rationalité sur les mots : clôture par complémentaire, accepteurs déterministes et complets, et caractérisation en logique du second ordre monadique. Nous établissons un lien étroit entre les automates à pile d'ordre supérieur et les ensembles rationnels de piles d'ordre supérieur. Notre seconde contribution est l'étude structurelle des graphes associés à ces automates. Nous en donnons différentes caractérisations qui montrent la robustesse de ces familles de graphes infinis.
21
Cristau, Julien. "Jeux et automates sur les ordres." Phd thesis, Université Paris-Diderot - Paris VII, 2010. http://tel.archives-ouvertes.fr/tel-00554026.
Full textAbstract:
Cette thèse aborde des sujets liés à la théorie des automates, à la logique et à la théorie des jeux. Ces thèmes sont au cœur de l'informatique théorique depuis de nombreuses décennies. Les travaux de recherche dans ces domaines sont motivés entre autres par des questions de modélisation et de vérification de systèmes. La première partie de la thèse considère les automates finis et la logique temporelle sur des ordres linéaires arbitraires. On y donne une procédure (doublement exponentielle en espace) pour décider la satisfaisabilité d'une formule LTL, utilisant une étape de transformation d'une formule logique en un transducteur synchrone. La seconde partie s'intéresse à des jeux de longueur ordinale. On propose un modèle de jeux à deux joueurs sur des graphes finis, et on montre que la question du vainqueur pour ces jeux peut être résolue en espace polynomial. De plus, on montre qu'il existe des stratégies gagnantes à mémoire finie.
22
Daviaud, Laure. "Comportements asymptotiques des automates Max-plus et Min-plus." Paris 7, 2014. http://www.theses.fr/2014PA077238.
Full textAbstract:
Ce mémoire porte sur l'étude de problèmes qui se situent à la frontière de décidabilité entre la décidabilité de l'existence de bornes et l'indécidabilité de la comparaison de fonctions. Pour cela, ce mémoire donne une description fine des fonctions calculées par automates min-plus et max-plus. Plus précisément, étant donnée une fonction f calculée par un automate min-plus (resp. Max-plus) la contribution principale du mémoire consiste en la description de la fonction g qui, à un entier n, associe le maximum des valeurs f(w) pour les mots w de longueurs inférieures à n (resp. Le minimum des valeurs f(w) pour les mots w de longueurs supérieures à n). Le théorème d'approximation du rapport fonction-longueur donne une approximation de la borne supérieure des rapports g(n)/n dans le cas d'un automate min-plus, et une approximation de la borne inférieure des rapports g(n)/n dans le cas d'un automate max-plus. Le théorème d'équivalence asymptotique décrit le comportement asymptotique de la fonction g dans le cas max-plus, et plus précisément, il est prouvé que cette fonction est asymptotiquement équivalente à une fonction rationnelle. Le théorème d'approximation du rapport fonction-longueur à une application à la comparaison approchée de fonctions calculées par automates min-plus. La comparaison obtenue raffine grandement les résultats déjà connus sur la comparaison de fonctions, et semble être la comparaison la plus précise qui reste décidable entre deux fonctions calculées par automates min-plus. Le théorème d'équivalence asymptotique exhibe un algorithme qui permet de calculer un équivalent asymptotique de la longueur de la plus longue exécution dans le modèle de la size-change abstractionThis thesis focuses on the study of issues that lie at the boundary between decidability of boundedness and undecidability of the comparison. For that, this paper gives a detailed description of functions computed by min-plus and max-plus automata. More precisely, given a function f computed by a min-plus (resp. Max-plus) automaton, the main contribution of the thesis consists in the description of the function g that associates an integer n to the maximum of the values f(w) for words w of length less than n (respectively the minimum of the values f(w) for words w of length greater than n). The theorem for approximating the function-length ratio gives an approximation of the upper bound of ratios g(n)/n in the case of a min-plus automaton, and an approximation of the lower bound of ratios g(n)/n in the case of a max-plus automaton. The asymptotic equivalence theorem describes the asymptotic behavior of the function g in the case of max-plus automata and more precisely, it states that this function is asymptotically equivalent to a rational function. The theorem for approximating the function-length ratio has an application to the approximate comparison of min-plus automata. This approximate comparison highly refines previously known results about comparison, and appears to be the most accurate comparison between two functions computed by min-plus automata, that remains decidable. The asymptotic equivalence theorem exhibits an algorithm that calculates an asymptotic equivalent of the length of the longest run in a size-change abstraction instance
23
Gonzalez, Patrick. "Croissance d'automates et théorie des nombres." Aix-Marseille 2, 1992. http://www.theses.fr/1992AIX22028.
Full textAbstract:
L'unicite de l'ecriture d'un entier, en base g, avec, pour chiffres, les elements d'un ensemble fini d'entiers naturels, peut se traduire par des contraintes sur les matrices des chemins d'un g-automate fini. En associant ces automates a des operateurs polynomiaux lies a la fonction generatrice du probleme, on en deduit, en faisant croitre la longueur des chemins, un critere polynomial permettant de decider de l'unicite ou de la non-unicite de l'ecriture pour tous les entiers lorsqu'elle existe
24
Hadj, Kacem Hatem. "Contributions à la théorie et aux applications des automates à multiplicités." Rouen, 2005. http://www.theses.fr/2005ROUES008.
Full textAbstract:
Ce mémoire de thèse est un travail autour de publications en Informatique Théorique. Il contient deux contributions à la théorie des automates à Multiplicités, structure qui s'applique avec succès aux sciences voisines (Informatique, Mathématique, Physique, …). Un type particulier d'automates à multiplicités est constitué des automates avec ε-transitions notés k-ε-automates. Dans la première partie, on donne une méthode algébrique pour éliminer les ε-transitions de ces k-ε-automates afin d'obtenir un k-automate équivalent ayant le même comportement. Nous discutons les deux aspects du problème de l'étoile (par somme infinie et par équations). La théorie de la minimisation permet de minimiser un k-automate, au sens de réduire au maximum son nombre d'états tout en conservant le même comportement. Elle peut être utilisée, avec une légère modification, pour résoudre d'autres problèmes. Deux applications sont développées : dans un premier temps, on a utilisé cet algorithme de décomposition pour casser des fonctions booléennes, qui constituent l'élément non linéaire des algorithmes cryptographiques. La deuxième application consiste à décomposer des ц-modules où ц est l'algèbre de Hecke à q=0This thesis is a work based on publications in Theoretical Computer Science. It consists of two contributions of the theory of automata with multiplicities. This structure has many applications to connected sciences (Computer Sciences, Mathematics, Physics, …). A particular type of automata with multiplicities is the automaton with ε-transitions denoted by k-ε-automaton. In the first part, we give an algebraic method for removing the ε-transitions of the k-ε-automaton in order to obtain an equivalent k-automaton with the same behaviour. We discuss two aspects of the star problem (by infinite sums and by equations). The theory of minimization allows to minimize a k-automaton in the sense of reducing to the smallest among the number of states. It can be used with some modification to solve other problems such as the splitting of modules. We have used the algorithm of decomposition to split a Boolean function which constitute the non linear element of the cryptographic algorithm and to split a ц-module where ц is the Hecke algebra as q=0
25
Bernardi, Vincent. "Lois de conservation sur automates cellulaires." Aix-Marseille 1, 2007. http://www.theses.fr/2007AIX11055.
Full textAbstract:
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.
26
Barat, Guy. "Echelles de numération et fonctions arithmétiques associées." Aix-Marseille 1, 1995. http://www.theses.fr/1995AIX11057.
Full textAbstract:
Differentes proprietes, principalement statistiques, des systemes de numeration et de leurs fonctions additives ou multiplicatives au sens de bellman et shapiro sont etudiees. Deux versions generales du lemme de coquet relatif aux moyennes de ces fonctions sont notamment etablies. Dans le cadre d-adique, une etude detaillee d'un procede universel d'extraction est effectuee en termes d'automaticite et de quasi-periodicite. Des resultats de delange sur la repartition des fonctions d-additives sont etendus a certaines echelles lineaires recurrentes, l'introduction de techniques ergodiques permettant en outre d'obtenir des proprietes de regularite et d'equidistribution, ces dernieres generalisant une construction due a van der corput
27
Ramangalahy, Solofo. "Test de conformité pour des spécifications à base d'automates : une approche par la théorie des jeux." Orléans, 1999. http://www.theses.fr/1999ORLE2073.
Full textAbstract:
Le test de conformité est l'activité qui consiste à confronter l'implantation d'un système à sa spécification initiale au moyen de tests, afin de s'assurer de sa correction. Le modèle des automates est sous-jacent à la sémantique des langages de spécification usuels. Leur utilisation dans la phase de spécification d'un système permet d'étudier le problème du test de conformité par l'approche dite des "méthodes formelles". Cette thèse aborde ce problème dans le cadre de cette approcheConformance testing aims at applying test cases to a system in order to study its correction with respect to its specification. The automaton model underlies the semantics of the usual formal specification languages. Its use in the specification phase allow the study of the conformance testing problem with the so-called "formal methods" framework. The thesis study this problem in this framework
28
Sebti, Nadia. "Noyaux rationnels et automates d'arbres." Rouen, 2015. http://www.theses.fr/2015ROUES007.
Full textAbstract:
Dans le cas des mots, un schéma général de calcul des noyaux rationnels a été proposé. Il repose sur un algorithme général de composition des transducteurs pondérés et un algorithme général de calcul de plus petite distances. Notre objectif est de généraliser ce schéma de calcul aux cas des arbres en utilisant les automates d’arbres. Pour ce faire, nous avons fixé les deux objectifs principaux suivants : D’une part, définir les automates d’arbres pour le calcul des noyaux des sousarbres, des sous-séquences d’arbres et des facteurs d’arbres. D’autre part, à partir d’une expression rationnelle d’arbres, construire un automate d’arbres pour le calcul des différents noyaux rationnels décrits par des expressions rationnelles d’arbres en utilisant le schéma suivant sur deux langages d’arbres L1 et L2 : KE (L1;L2) = (AL1 \ AE \ AL2). Nous avons exploré et proposé des algorithmes efficaces pour la conversion d’une expression rationnelle d’arbres en automates d’arbres. Le premier algorithme calcule, à partir d’une expression rationnelle d’arbres E de taille jEj et de largeur alphabétique jjEjj, les ensembles Follow en temps O(jjEjj jEj). Le second algorithme calcule l’automate d’arbres des équations via les k-C-Continuations qui est basé sur la minimisation acyclique de Revuz. Cet algorithme calcule l’automate des équations avec une complexité e temps et en espace en O(jQj jEj) où jQj est le nombre d’états de l’automate produit. Ensuite, nous avons conçu des algorithmes pour le calcul des noyaux des sous-arbres, des sous-séquences d’arbres et des facteurs d’arbres. Notre Approche est basée sur la représentation de l’ensemble d’arbres S = fs1; : : : ; sng (resp. T = ft1; : : : ; tmg) par un automate d’arbres pondéré particulier baptisé Root Automate d’Arbres Pondéré, le RAAP AS (resp. AT ) (équivalent à l’automate des préfixes dans le cas des mots) tel que jASj Pn P i=1 jsij = jSj (resp. JAT j # m j=1 jtj j = jTj) ; puis de calculer les noyaux entre les deux ensembles S et T. Ceci revient au calcul du poids de l’automate intersection AS \ AT. Nous montrons que le calcul du noyau K(S; T) peut se faire en temps et en espace O(jASj jAT j)In the case of words, a general scheme for computing rational kernels has been proposed. It is based on a general algorithm for composition of weighted transducers and a general algorithm computing smallest distance. Our goal is to generalize this computation scheme to the case of trees using tree automata. To do this we have established the following two main objectives : On the one hand,define tree automata for computing subtree kernel, subsettree kernel and tree factor kernel. On the other hand, from a regular tree expression, build a tree automaton to compute the various rational tree kernels described by regular tree expressions using the following scheme over two tree languages L1 and L2 : KE(L1;L2) = (AL1 \ AE \ AL1). We explored and proposed efficient algorithms for the conversion of a regular tree expression into tree automata. The first algorithm computes the Follow sets for a regular tree expression E of a size jEj and alphabetic width jjEjj in O(jjEjj jEj) time complexity. The second algorithm computes the equation tree automaton via the k-C-Continuations which is based on the acyclic minimization of Revuz. The algorithm is performed in an O(jQj jEj) time and space complexity, where jQj is the number of states of the produced automaton. Then we developed algorithms for the computation of subtree kernel, subsettree kernel and tree factor kernel. Our approach is based on the representation of all trees of the set S = fs1; : : : ; sng (resp. T = ft1; : : : ; tmg) by a particular weighted tree automaton called Root Weighted Tree Automaton the RWTA AS (resp. AT ) (equivalent to the prefix automaton in the case of words) such that jASj #Pn i=1 jsij = jSj (resp. JAT #Pm j=1 jtj j = jTj) ; then we compute the kernels between the two sets S and T. This amounts to compute the weight of the intersection automaton AS \ AT. We show that the computation of the kernel K(S; T) can be done in O(jASj jAT j) time and space complexity. Keywords: Finite Tree Automata, Rationnal Tree Languages, Regular Tree Expressions, Conversion of Regular Tree Expressions, Rational Kernels, Trees, Rational Tree Kernels
29
Genet, Thomas. "Contraintes d'ordre et automates d'arbres pour les preuves de terminaison." Nancy 1, 1998. http://docnum.univ-lorraine.fr/public/SCD_T_1998_0245_GENET.pdf.
Full textAbstract:
Les systèmes de réécriture sont des systèmes de calcul simples et lisibles dont l'expressivité est suffisante pour le codage des programmes ou la spécification de processus automatiques. En exprimant les programmes ou processus sous la forme de systèmes de réécriture, on dispose, en outre, d'outils de vérification puissants basés sur les méthodes de preuve de la réécriture. La terminaison assure l'achèvement des calculs en un temps fini et elle est une prémisse indispensable à d'autres méthodes de preuve telle la preuve par récurrence. Classiquement, la preuve de terminaison d'un système de réécriture utilise la recherche d'un ordre bien fondé assurant la décroissance de chaque étape de réécriture. La recherche manuelle d'un tel ordre n'est envisageable que sur des petits systèmes. C'est pourquoi l'automatisation des preuves de terminaison est un élément crucial pour l'exploitation des outils de preuve de la réécriture sur des programmes ou des processus de taille réelle. Dans cette thèse nous présentons deux approches pour l'automatisation des preuves de terminaison des systèmes de réécriture. Dans la première approche, la recherche de l'ordre de terminaison - une instance de l'ordre général sur les chemins (GPO) - est effectuée a l'aide d'un mécanisme de résolution de contraintes d'ordre (sur des graphes orientés) tendant à rendre la recherche efficace et automatique. La deuxième approche est modulaire ; le système est divisé en sous-systèmes et les preuves de terminaison sont réalisées indépendamment pour chaque sous-système. La terminaison du système complet est assurée, pour une certaine stratégie d'application des sous-systèmes, par un critère basé sur le calcul d'une approximation de l'ensemble des formes normales en utilisant des techniques d'automates d'arbres. D'autres applications de cette approximation sont également présentées, parmi lesquelles la complétude suffisante, le test d'atteignabilité, et la preuve de non-terminaison forte.
30
Cécé, Gérard. "Vérification, analyse et approximations symboliques des automates communicants." Cachan, Ecole normale supérieure, 1998. http://www.theses.fr/1998DENS0008.
Full textAbstract:
Nous nous intéressons à l'étude de l'un des modèles de l'algorithmique repartie : les automates communicants. Ce modèle est particulièrement indiqué pour la description de protocoles de communication, et constitue la base théorique de langages de description formelle tels Estelle et sdl. Ce modèle a toutefois la particularité d'être aussi expressif que les machines de Turing. Nous avons alors investi deux approches complémentaires. La première est de s'inspirer de contraintes réelles, soit physiques soit de modélisation, pour restreindre l'expressivité du modèle et gagner ainsi en possibilités d'analyse. Nous considérons tout d'abord trois défaillances (la perte, l'insertion ou la duplication de messages), et leurs diverses combinaisons, pouvant apparaitre dans les canaux de communication. Nous montrons que les erreurs d'insertion de messages entrainent une plus forte diminution de la puissance du modèle que les erreurs de perte de messages. Par contre, les erreurs de duplication de messages n'affectent pas la puissance du modèle, et sont même récupérables. Nous considérons aussi la communication half-duplex. Ce mode interdit à 2 entités de s'envoyer des messages simultanément (contrairement au mode full-duplex). Dans le cas de 2 automates, nous montrons que de nombreuses possibilités de vérification s'offrent à nous, mais que ce n'est plus le cas a partir de trois automates. La seconde approche consiste à garder intacte la puissance de description du modèle, et a mettre en œuvre des semi-algorithmes de verification (c'est-a-dire sans garantie de terminaison). Pour cela, nous nous sommes intéressés à la notion de transitions symboliques, qui permettent de vérifier en un nombre fini d'étapes, une infinité d'états d'un système. Nous proposons deux types de transitions symboliques, les communications à émissions non consommées et les émissions linéaires, qui permettent de généraliser de façon significative des résultats récents de la littérature.
31
Renkin, Florian. "Transformations d’ω-automates pour la synthèse de systèmes réactifs." Electronic Thesis or Diss., Sorbonne université, 2022. http://www.theses.fr/2022SORUS227.
Full textAbstract:
La synthèse vise à produire un système correct à partir de spécifications. Une approche pour résoudre ce problème consiste à traduire la spécification en un jeu de parité dont la stratégie gagnante encode le système. Dans cette thèse nous allons montrer deux méthodes permettant de produire des automates de parité. La première s'appuie sur l'amélioration et la combinaison de procédures nouvelles ou existantes. La seconde est un algorithme de Casares et al. apportant une garantie d'optimalité du résultat. Dans un deuxième temps, nous montrerons comment nous réduisons le système obtenu. Deux types de réductions seront abordées. La première permet d'obtenir un résultat optimal mais pas la seconde qui privilégie le temps de traitement. La troisième partie décrira des optimisations qui peuvent être utilisées pour certaines classes de spécificationsSynthesis aims to produce a correct system from specifications. One approach to solve this problem is to translate the specification into a parity game whose winning strategy encodes the system. In this thesis we will show two methods to produce parity automata. The first is based on improving and combining new or existing procedures. The second is an algorithm from Casares et al. providing a guarantee of optimal results. In a second step, we will show how we reduce the obtained system. Two types of reductions will be discussed. The first allows to obtain an optimal result but not the second which privileges the processing time. The third part will describe optimizations that can be used for certain classes of specifications
32
Gauwin, Olivier. "Flux XML, Requêtes XPath et Automates." Phd thesis, Université des Sciences et Technologie de Lille - Lille I, 2009. http://tel.archives-ouvertes.fr/tel-00421911.
Full textAbstract:
Ces dernières années, XML est devenu le format standard pour l'échange de données. Les documents XML sont généralement produits à partir de bases de données, durant le traitement de documents, ou au sein d'applications Web. L'échange de données en flux est fréquemment utilisé lors de l'envoi de données volumineuses par le réseau. Ainsi le transfert par flux est adéquat pour de nombreux traitements XML.Dans cette thèse, nous étudions des algorithmes d'évaluation de requêtes sur des flux XML. Notre objectif est de gérer efficacement la mémoire, afin de pouvoir évaluer des requêtes sur des données volumineuses, tout en utilisant peu de mémoire. Cette tâche s'avère complexe, et nécessite des restrictions importantes sur les langages de requêtes. Nous étudions donc les requêtes définies par des automates déterministes ou par des fragments du standard W3C XPath, plutôt que par des langages plus puissants comme les standards W3C XQuery et XSLT.
Nous définissons tout d'abord les Streaming Tree Automata (STAs), qui opèrent sur les arbres d'arité non bornée dans l'ordre du document. Nous prouvons qu'ils sont équivalents aux Nested Word Automata et aux Pushdown Forest Automata. Nous élaborons ensuite un algorithme d'évaluation au plus tôt, pour les requêtes définies par des STAs déterministes. Bien qu'il ne stocke que les candidats nécessaires, cet algorithme est en temps polynomial à chaque événement du flux, et pour chaque candidat. Par conséquent, nous obtenons des résultats positifs pour l'évaluation en flux des requêtes définies par des STAs déterministes. Nous mesurons une telle adéquation d'un langage de requêtes à une évaluation en flux via un nouveau modèle de machines, appelées Streaming Random Access Machines (SRAMs), et via une mesure du nombre de candidats simultanément vivants, appelé concurrence. Nous montrons également qu'il peut être décidé en temps polynomial si la concurrence d'une requête définie par un STA déterministe est bornée. Notre preuve est basée sur une réduction au problème de la valuation bornée des relations reconnaissables d'arbres.
Concernant le standard W3C XPath, nous montrons que même de petits fragments syntaxiques ne sont pas adaptés à une évaluation en flux, sauf si P=NP. Les difficultés proviennent du non-déterminisme de ce langage, ainsi que du nombre de conjonctions et de disjonctions. Nous définissons des fragments de Forward XPath qui évitent ces problèmes, et prouvons, par compilation vers les STAs déterministes en temps polynomial, qu'ils sont adaptés à une évaluation en flux.
33
Mansard, Alexandre. "Automates infinis et traces de Mazurkiewicz." Thesis, La Réunion, 2020. https://elgebar.univ-reunion.fr/login?url=http://thesesenligne.univ.run/20_22_A_Mansard.pdf.
Full textAbstract:
Nous introduisons la notion de régularité par niveaux pour des langages de traces de Mazurkiewicz et nous considérons des systèmes reconnaissables de réécriture de traces, à contextes réguliers par niveaux (RTL). Nous prouvons qu’un automate dont le graphe sous-jacent est le graphe de réécriture d’un système RTL et dont les ensembles de sommets initiaux et finaux sont réguliers par niveaux (automate RTL), est mot-automatique. En particulier, la théorie du premier ordre d’un automate RTL est décidable. Ensuite, nous prouvons que, enrichi de la relation d’accessibilité, un automate dont le graphe sous-jacent est déplié concurrent d’un graphe fini concurrent et dont les ensembles de sommets initiaux et finaux sont réguliers par niveaux, est RTL. En particulier, la théorie du premier ordre avec accessibilité d’un tel automate est décidable. Par ailleurs, il est bien connu que la théorie du premier ordre avec accessibilité du graphe de réécriture suffixe d’un système de réécriture de termes clos (graphe GTR) est décidable. Nous mettons en évidence divers dépliés concurrents de graphes finis concurrents qui ne sont pas des graphes GTR. L’arbre du quart de la grille infinie est un exemple de tel déplié. La classe des dépliés concurrents des graphes finis concurrents constitue ainsi une classe de DAG mot-automatiques, dont la théorie du premier ordre avec accessibilité est décidable et qui contient des graphes non GTR. Nous définissons pour les automates de traces (automates dont les sommets sont des traces de Mazurkiewicz) deux opérations que sont la synchronisation par niveaux et la superposition par niveaux et nous montrons que si une famille F d’automates de traces est fermée pour ces opérations, alors pour tout automate déterministe H 2 F, les langages acceptés par les automates déterministes de F qui sont longueur-réductibles en H forment une algèbre de Boole ; la longueur d’une trace étant donnée par la longueur de sa forme normale de Foata, un automate de traces G est longueur-réductible dans un automate de traces H, s’il existe un morphisme de G dans H préservant la longueur. Ensuite, nous montrons que la classe des automates suffixes de traces à contextes réguliers par niveaux, qui n’est que l’extension aux traces de Mazurkiewicz des automates suffixes de mots, satisfait ces propriétés de fermeture. Nous appelons réseau de Petri généralisé un automate suffixe de traces sur un alphabet de dépendance pour lequel la dépendance est réduite à l’égalité. Nous montrons alors que la sous-famille des réseaux de Petri généralisés satisfait également les propriétés de fermeture ci-dessus. Cela conduit notamment à 5 diverses algèbres de Boole de langages acceptés par des réseaux de Petri généralisés déterministesWe introduce the notion of level-regularity for Mazurkiewicz trace languages and we consider recognizable trace rewriting systems with level-regular contexts (RTLsystem). We prove that an automaton for which the underlying graph is the rewriting graph of a RTL system and for which the sets of initial vertices and final vertices are level-regular (RTL automaton), is word-automatic. In particular, the first-order theory of a RTL automaton is decidable. Then, we prove that, enriched with thereachability relation, an automaton for which the underlying graph is the concurrent unfolding of a finite concurrent graph, and for which the sets of initial vertices and final vertices are level-regular, is RTL. In particular, the first-order theory with the reachability predicate of such an automaton is decidable. Besides, it is known that this property also holds for ground term rewriting graphs (GTR graph). We highlight various concurrent unfoldings of finite concurrent graphs that are not GTRgraphs. The infinite quarter grid tree is such an unfolding. The class of concurrent unfoldings of finite concurrent graphs is therefore a class of word-automatic graphs for which the first-order theory with the reachability predicate is decidable and that contains some non GTR graphs. We define the operations of level-length synchronization and level-length superposition of trace automata (automata for which vertices are Mazurkiewicz traces) and we prove that if a family F of trace automata is closed under these operations, then for any deterministic trace automaton H 2 F, the languages accepted by the deterministic trace automata belonging to F and that are length-reducible to H, form a Boolean algebra; the length of a trace being the length of its Foata normal form, a trace automaton G is length-reducible to a trace automaton H if there exists a length-preserving morphism from G to H. Then, we show that the family of trace suffix automata with level regular contexts, the extension of word suffix automata to Mazurkiewicz traces, satisfies these closure properties. We define a generalized Petri net as a trace suffix automaton over a dependence alphabet for which the dependence is reduced to the equality and we show that the subfamily of generalized Petri nets also satisfies the closure properties above. In particular, this yields various Boolean algebras of word languages accepted by deterministic generalized Petri nets
34
Zeitoun, Marc. "Opérations implicites et variétés de semi-groupes finis." Paris 7, 1993. http://www.theses.fr/1993PA077221.
Full textAbstract:
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
35
Héam, Pierre-Cyrille. "Contribution à l'algorithmique des automates : compléxité et aspects topologiques." Paris 7, 2001. http://www.theses.fr/2001PA077085.
Full text
36
Maniatakos, Vasileios Foivos A. "Graphes et Automates pour le Contrôle de l'Interaction en Improvisation Musicale Assistée par Ordinateur." Paris 6, 2012. http://www.theses.fr/2012PA066249.
Full textAbstract:
Cette thèse concerne l'interaction en trois parties dans le contexte d'improvisation musicale assistée par ordinateur (IAO). Cette terme veut décrire l'ensemble des interactions émergentes par la co-existance sur scène des trois types d'acteurs: des instrumentistes, des ordinateurs des opérateurs d'ordinateur. L'objective de cette recherche est d'étudier les conditions nécessaires pour une telle interaction, ainsi que d'établir le cadre théorique permettant à l'ordinateur d'accomplir une double mission: celle d'un jouer ainsi que d'un instrument. Dans ce cadre on introduit le Graphe en Facteurs Multiples (MFG), qui est un nouveau modèle de mémoire pour les séquences musicales. MFG est un automate déterministe pour l'indexation des séquences jouées, ayant comme but de répondre aux problèmes de reconnaissance de paternes ainsi que de génération des séquences. Inspiré par l'automate de l'Oracle des Facteurs (FO), MFG vise à: 1)corriger les faux positives dans la reconnaissance des mots et 2) corriger -concernant le domaine de IAO- les erreurs d'estimation des probabilités des continuations qui se font sur la base de l'arbre des suffixes de FO. Dans un deuxième temps, cette thèse fait appel à la théorie de graphes, afin d'étudier des problèmes du contrôle de la génération des séquences symboliques. En suite, nous proposons des modèles computationels basés sur des graphes pour confronter des problèmes relevants. Dans le dernière partie de cette thèse, nous démontrons l'utilité de MFG du point de vue d'un modèle universel pour des taches musicals divers, notamment l'écoute musicale, la génération des séquences par contraintes et l'interactionThis thesis studies three party interaction in the music improvisation context. We use this term to refer to the ensemble of interactions arising from the onstage coexistence of three constituents participants: the human instrument player, the computer and the computer operator/performer. The purpose of this study is to investigate the requirements arising out of such interaction as well as establish the framework that will allow the computer fulfil the double mission of operating both as player and an instrument. In this framework we first present Multi Factor Graph (MFG), a new memory model for musical sequences. MFG is a deterministic automaton that indexes played sequences, with the intention of dealing with pattern recognition and sequence generation. Inspired by the Factor Oracle (FO) automaton, MFG deals with two FO-related issues. First, it corrects FO’s false positives during string recognition. Second, as far as the computer improvisation domain is concerned, it corrects the errors in the estimation of continuation probabilities arising from the misinterpretation of the FO’s Suffix Link Tree (SLT) as an indicator for maximal suffix repeats. Secondly, we study with the help of graphs by examining the complexity of adding simple to more sophisticated and complex constraints to generation. We propose reduced, graph-based computational frameworks that are able to efficiently deal with each of the problems discussed earlier. Finally, by drawing together all elements developed throughout the first two parts, we employ MFG as a universal framework for managing problems of machine musicianship, namely music listening, constrained sequence generation and interaction
37
De, Souza Rodrigo. "Etude structurelle des transducteurs de norme bornée." Paris, ENST, 2008. http://www.theses.fr/2008ENST0023.
Full textAbstract:
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 connusTransducers - 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
38
Devolder-Muchembled, Jeanne. "Codes, mots infinis et bi-infinis." Lille 1, 1993. http://www.theses.fr/1993LIL10075.
Full textAbstract:
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
39
Rispal, Chloé. "Automates sur les ordres linéaires : Complémentation." Phd thesis, Université de Marne la Vallée, 2004. http://tel.archives-ouvertes.fr/tel-00720658.
Full textAbstract:
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.
40
Sablik, Mathieu. "Etude de l'action conjointe d'un automate cellulaire et du décalage : une approche topologique et ergodique." Aix-Marseille 2, 2006. http://www.theses.fr/2006AIX22019.
Full text
41
Guillon, Pierre. "Automates cellulaires : dynamiques, simulations, traces." Phd thesis, Université Paris-Est, 2008. http://tel.archives-ouvertes.fr/tel-00432058.
Full textAbstract:
Un automate cellulaire est un système dynamique discret qui modélise des objets ayant une évolution parallèle synchrone: l'espace est divisé en cellules ayant chacune un état et qui évoluent toutes selon une même règle locale, qui ne dépend que d'un nombre fini de cellules voisines. Malgré la simplicité de la formalisation de ce système, des comportements très complexes peuvent apparaître, qui en font notamment un modèle de calcul. Cette complexité a été rattachée à diverses théories: topologie, mesure, décidabilité, information...Nous adoptons ici une approche basée sur la dynamique symbolique, c'est à dire l'étude des mots infinis sur un alphabet donné auxquels on applique un décalage, suppression de la première lettre. À chaque automate cellulaire peut en effet être associé son tracé, l'ensemble des mots infinis représentant la séquence des états successifs pris par la cellule centrale de l'espace - ou un groupe de cellules centrales. On a alors une factorisation topologique: la lecture d'une lettre dans un de ces mots correspond exactement à une étape de l'évolution de l'automate. De nombreuses propriétés topologiques sont alors transmises par cette factorisation. Inversement, le fait que les cellules évoluent toutes de la même manière permet de déduire certaines propriétés de l'automate à partir de celles de son tracé. La première partie de la thèse est consacrée à ces nombreux liens. Une deuxième partie présente des conditions suffisantes pour qu'un ensemble de mots infinis soit le tracé d'un automate cellulaire. Enfin, une troisième partie donne un point de vue plus informatique, en récapitulant les principaux résultats d'indécidabilité sur le sujet et en prouvant que toutes les propriétés du tracé qui peuvent se voir infiniment tard sont indécidables
42
Frilley, François. "Differenciation d'ensembles structures : applications aux cas du monoïde libre et de la foret des arbres finis et étiquetés." Paris 7, 1989. http://www.theses.fr/1989PA077189.
Full textAbstract:
La manipulation d'objets structures est un aspect essentiel de l'informatique moderne, en particulier dans les systèmes d'aide a la programmation. L'objet de cette thèse est l'étude de la comparaison de ces structures, qui est importante, tant d'un point de vue théorie que d'un point de vue pratique. Mathématiquement, tous les problèmes de comparaison appartiennent à un même paradigme décrit simplement par la notion de différenciation étudiée dans la première partie. Les exemples très importants de la différenciation sur le monoïde libre et sur la foret des arbres étiquetés sont ensuite abordes. Le premier de ces deux exemples a été souvent étudie: seule une synthèse des principaux résultats afférents au problème, complétée par une importante bibliographie, est présentée ici. Le deuxième, par contre, est totalement original. Il est aborde a la fois sous un aspect théorique, montrant la difficulté du sujet et sous un aspect pratique permettant de construire un différenciateur d'arbres applicable a un système réel a caractère industriel: l'éditeur syntaxique Centaur
43
Frisch, Alain. "Théorie, conception et réalisation d'un langage de programmation adapté à XML." Paris 7, 2004. http://www.theses.fr/2004PA077074.
Full text
44
Dando, Louis-Marie. "Expressivité des automates pondérés circulaires et boustrophédons." Thesis, Bordeaux, 2019. http://www.theses.fr/2019BORD0130/document.
Full textAbstract:
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 classsiquesThis 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
45
Luque, Jean-Gabriel. "Monoïdes et automates admettant un produit de mélange." Rouen, 1999. http://www.theses.fr/1999ROUES094.
Full textAbstract:
Cette thèse est consacrée à l'étude des monoïdes et des automates admettant un produit de mélange. Les deux premiers chapitres sont dédiés aux monoïdes des traces (qui est un cas particulier de monoïde admettant un produit de mélange). Le premier traite de la généralisation aux traces du procédé d'élimination de Lazard. Nous étudions en particulier les bissections de type Lazard dont les deux facteurs sont partiellement commutatifs libres. Par composition, nous fabriquons des factorisations complètes et par crochetages des bases de l'algèbre de Lie partiellement commutative libre. Nous donnons, pour une famille d'alphabets à commutations, une généralisation des ensembles de Hall. Le second chapitre soulève le problème de la caractérisation des éléments du support des algèbres de Lie partiellement commutatives libres. Nous décrivons une famille d'alphabets à commutations pour laquelle cette caractérisation est très proche de celle du cas libre. Le troisième chapitre est consacré à la caractérisation des congruences compatibles avec le produit de mélange. Nous montrons que les commutations partielles sont le cadre maximal pour l'existence d'un produit de mélange lorsque les multiplicités sont dans un non-anneau ou dans un anneau de caractéristique non première. Dans le cas de la caractéristique première, nous donnons une décomposition de ces congruences en parties primitives. Nous montrons également que le mélange de deux automates saturés par une congruence compatible est lui aussi sature. Le dernier chapitre traite de ma participation au projet SEA, et en particulier de la réalisation d'un algorithme de minimisation pour des automates à multiplicités dans un anneau principal.
46
VELOSO, PEIXOTO MARCOS. "Automates a contraintes arithmetiques et procedures d'evaluation ascendante de programmes logiques." Paris 7, 1994. http://www.theses.fr/1994PA077194.
Full textAbstract:
Cette these se divise en deux parties: la premiere partie presente un modele permettant de representer des systemes concurrents parametres (c'est-a-dire, manipulant une quantite non bornee de donnees). On montrera dans cette premiere partie que le probleme de verification de proprietes de ces systemes se ramene a un probleme d'evaluation ascendante de programmes logiques. Dans la deuxieme partie, nous apportons une contribution au probleme du calcul du resultat de l'evaluation ascendante de programmes logiques avec des contraintes arithmetiques. Nous definissons une classe de programmes logiques sur des entiers dans laquelle le processus d'evaluation ascendante engendre toujours une formule arithmetique lineaire. Un programme appartenant a cette classe contient au plus trois regles recursives, qui possedent, chacune, un seul atome arithmetique dans le corps. Nous adoptons une approche geometrique pour construire le resultat du processus d'evaluation ascendante
47
Maubert, Bastien. "Fondations logiques des jeux à information imparfaite : stratégies uniformes." Phd thesis, Université Rennes 1, 2014. http://tel.archives-ouvertes.fr/tel-00980490.
Full textAbstract:
On trouve dans la littérature de nombreux exemples de jeux où les stratégies souhaitées sont soumises à des contraintes ''transversales'' portant sur des ensembles de parties, reliées entre elles par quelque relation sémantique. L'exemple le plus fameux est celui des stratégies dans les jeux à information imparfaite, et les jeux où la condition de gain a un aspect épistémique en sont d'autres. Cependant, aucune étude approfondie n'a à notre connaissance été menée sur ce type de contraintes dans leur généralité. C'est ce que nous nous proposons de commencer dans cette thèse. Nous définissons donc une notion générale de stratégies uniformes. Les propriétés d'uniformité des stratégies sont exprimées dans un langage logique qui étend CTL∗ avec deux quantificateurs originaux. Ces quantificateurs sont très proches des opérateurs de connaissance classiques en logique épistémique, et font intervenir des ensembles de parties reliées entre elles par des relations binaires. Nous montrons comment cette notion de stratégies uniformes capture les exemples connus de la littérature, puis nous étudions en profondeur le problème de la synthèse de stratégies uniformes, en considérant que les relations binaires entre les parties sont reconnaissables par des automates finis (relations rationnelles). Nous établissons plusieurs résultats de décidabilité et de complexité, reposant largement sur des techniques d'automates : nous introduisons notamment comme outils les automates d'arbres bondissants et les automates d'ensembles d'informations. Par ailleurs, nos résultats permettent d'améliorer des résultats existants et d'en établir de nouveaux, dans les domaines du model-checking des logiques temporelles et épistémiques, ainsi que de la planification épistémique.
48
Guingne, Franck. "Contribution à l’algorithmique des automates pondérés à une, deux ou plusieurs bandes." Rouen, 2005. http://www.theses.fr/2005ROUES009.
Full textAbstract:
Les travaux présentés dans ce mémoire se situent dans le cadre de la théorie des automates. Une étude générale des relations de similarité et la notion d'automate couvrant sont présentés. On définit les relations de fusion ainsi que la notion de transducteur couvrant. Un algorithme de réduction est proposé et expérimenté. Les automates multi-bandes pondérés sont une généralisation des automates et transducteurs. On définit des opérations de jointure et d'auto-intersection et on présente les algorithmes correspondants. Une conséquence du Problème de Correspondance de Post est qu'il n'existe pas d'algorithme général d'auto-intersection. On définit alors une classe d'automates multi-bandes pondérés dans laquelle il est possible de calculer l'auto-intersection. Après un état de l'art des logiciels manipulant les machines d'état finis, on présente les compilateurs d'états finis de XEROX, WFSC et XFST, à travers leurs spécificités. On présente le symbole '?' et les machines à alphabet étendu, puis la notion de réseau virtuel dans XFST. Plusieurs caractéristiques de la conception générique et modulaire de WFSC sont exposées. On propose une étude de la complexité au pire des cas de l'impression de tous les chemins d'un automate acyclique. On décrit la structure qui maximise la complexité, et on calcule cette complexité pour un nombre d'états donnéThis PhD thesis deals with the automata theory. A general study of similarity relations and the notion a cover automata are presented. We define merging relations and the notion of cover transducers. A reduction algorithm is exposed and tested. Weighted multi-tape automata are a generalisation of automata and transducers. We define the join and auto-intersection operations and we present the corresponding algorithms. As a consequence of the Post's Correspondence Problem there does not exist a general algorithm of auto-intersection. We define a class of weighted multi-tape automata in which it is possible to compute the auto-intersection. After a State of the Art of finite state machine compilers, we present XEROX's compilers, WFSC and XFST, through their specificities. We present the '?' symbol and extended-alphabet machines, then the notion of virtual networks in XFST. Several characteristics of the generic and modular design of WFSC are exposed. We study the worst-case complexity for the printing of all paths of an acyclic automaton. We describe the structure that maximizes the complexity, then we compute this complexity for a given number of states
49
Saidane, Faouzi. "Graphes et langages : une approche métrique." Lyon 1, 1991. http://www.theses.fr/1991LYO10206.
Full textAbstract:
Cette these presente un point de vue categorique des systemes de transitions et illustre sa pertinence par des applications en theorie des graphes. Ce point de vue consiste, d'apres m. Pouzet et i. Rosenberg a considerer un systeme de transitions comme une sorte d'espace metrique; la distance entre deux etats etant, non pas un nombre, mais le langage accepte par l'automate constitue du systeme de transitions et de ces deux etats comme etats initiaux et finaux. Par exemple, voyant un graphe comme un systeme de transitions sur l'alphabet a deux lettres a et b muni de l'involution echangeant a et b, on retrouve la distance zigzag introduite par quilliot en 1983 pour les graphes. Si on ordonne les langages par l'ordre inverse de l'inclusion, alors les morphismes de systeme de transitions deviennent des applications contractantes; ainsi les idees issues de l'abondante etude des contractions d'espaces metriques peuvent etre appliquees aux systemes de transitions. Considerant des systemes de transitions involutifs nous decrivons les langages acceptes; notre description utilise un ordre sous les mots qui peut se definir a partir d'une regle de reecriture possedant la propriete de church-rosser. Nous en tirons une caracterisation des retractes absolus parmi ces systemes, semblable a celle obtenue par aronszajn et panichpakdi en 1956 pour les espaces metrique. Comme application nous obtenons, en collaboration avec h. -j. Bandelt et m. Pouzet, que la classe des graphes antisymetriques est la plus large classe de graphes ayant les retractes de produits de zigzags (reflexifs et antisymetriques) comme retractes absolus
50
Viêt, Triêm Tông Valérie. "Automates d'arbres et réécriture pour l'étude de problèmes d'accessibilité." Rennes 1, 2003. http://www.theses.fr/2003REN10162.
Full textAbstract:
L'objectif de cette thèse était d'étendre des techniques de réécriture sur les automates d'arbres afin de pouvoir les utiliser pour étudier des propriétés de sécurité sur les protocoles cryptographiques. Notre première partie présente la complétion d'automates d'arbres, procédé qui permet de calculer un automate reconnaissant un sur-ensemble des termes atteignables par un système de réécriture à partir d'un langage initial régulier. Nous proposons une condition dite de linéarité sur les automates permettant d'étendre le calcul aux systèmes de réécriture non linéaires à gauche, une condition sur la fonction d'approximation permettant de rendre le calcul des descendants exact. D'un point de vue algorithmique, nous présentons un algorithme de recherche des instances d'un terme dans un automate qui accelère la complétion. Nous avons implémenté ces résultats dans Timbuk, qui est un logiciel réalisé en Caml et disponible librement à l'URL \it http://www. Irisa. Fr/lande/genet/timbuk/. La deuxième partie de notre travail a été d'utiliser les techniques de complétion décrites précédemment pour vérifier des protocoles cryptographiques. Nous proposons l'exemple de la vérification du protocole View Only de SmartRight développé par Thomson Multimédia et qui vise à protéger des données numériques. La dernière partie de ce travail s'intéresse à la preuve automatique de propriétés initiales. Nous étudions les méthodes de démonstrations automatiques: récurrence explicite, récurrence par réécriture et preuve par cohérence. Nous proposons en premier lieu un algorithme de preuve de propriétés initiales, avant de montrer comment il est possible d'utiliser la complétion d'automates pour automatiser cet algorithme.