Academic literature on the topic 'Théorie algébgrique des automates'

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

RésuméLe problème de Jung-Nagata (cf. [J], [N]) consiste à savoir s'il existe des automorphismes dek[x; y; z] qui ne sont pas modérés. Nous proposons une approche nouvelle de cette question, fondée sur l'utilisation de la théorie des automates et du polygone de Newton. Cette approche permet notamment de généraliser de façon significative les résultats de [A].

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

We relate the problem of computing the closure of a finitely generated subgroup of the free group in the pro-V topology, where V is a pseudovariety of finite groups, with an extension problem for inverse automata which can be stated as follows: given partial one-to-one maps on a finite set, can they be extended into permutations generating a group in V? The two problems are equivalent when V is extension-closed. Turning to practical computations, we modify Ribes and Zalesskiĭ's algorithm to compute the pro-p closure of a finitely generated subgroup of the free group in polynomial time, and to effectively compute its pro-nilpotent closure. Finally, we apply our results to a problem in finite monoid theory, the membership problem in pseudovarieties of inverse monoids which are Mal'cev products of semilattices and a pseudovariety of groups. Résumé: Nous établissons un lien entre le problème du calcul de l'adhéerence d'un sous-groupe finiment engendré du groupe libre dans la topologie pro-V, oú V est une pseudovariété de groupes finis, et un probléme d'extension pour les automates inversifs qui peut être énoncé de la faç con suivante: étant données des transformations partielles injectives d'un ensemble fini, peuvent-elles être étendues en des permutations qui engendrent un groupe dans V? Les deux problèmes sont équivalents si V est fermée par extensions. Nous intéressant ensuite aux calculs pratiques, nous modifions l'algorithme de Ribes et Zalesskiĭ pour calculer l'adhérence pro-p d'un sous-groupe finiment engendré du groupe libre en temps polynomial et pour calculer effectivement sa clôture pro-nilpotente. Enfin nous appliquons nos résultats à un problème de théorie des monoïdes finis, celui de de l'appartenance dans les pseudovariétés de monoïdes inversifs qui sont des produits de Mal'cev de demi-treillis et d'une pseudovariété de groupes.

International audience For a real number $β >1$, we say that a permutation $π$ of length $n$ is allowed (or realized) by the $β$-shift if there is some $x∈[0,1]$ such that the relative order of the sequence $x,f(x),\ldots,f^n-1(x)$, where $f(x)$ is the fractional part of $βx$, is the same as that of the entries of $π$ . Widely studied from such diverse fields as number theory and automata theory, $β$-shifts are prototypical examples of one-dimensional chaotic dynamical systems. When $β$ is an integer, permutations realized by shifts have been recently characterized. In this paper we generalize some of the results to arbitrary $β$-shifts. We describe a method to compute, for any given permutation $π$ , the smallest $β$ such that $π$ is realized by the $β$-shift. Pour un nombre réel $β >1$, on dit qu'une permutation $π$ de longueur $n$ est permise (ou réalisée) par $β$-shift s'il existe $x∈[0,1]$ tel que l'ordre relatif de la séquence $x,f(x),\ldots,f^n-1(x)$, où $f(x)$ est la partie fractionnaire de $βx$, soit le même que celui des entrées de $π$ . Largement étudiés dans des domaines aussi divers que la théorie des nombres et la théorie des automates, les $β$-shifts sont des prototypes de systèmes dynamiques chaotiques unidimensionnels. Quand $β$ est un nombre entier, les permutations réalisées par décalages ont été récemment caractérisées. Dans cet article, nous généralisons certains des résultats au cas de $β$-shifts arbitraires. Nous décrivons une méthode pour calculer, pour toute permutation donnée $π$ , le plus petit $β$ tel que $π$ soit réalisée par $β$-shift.

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 variables
The 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

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.

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

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)

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

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

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.

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épart
The 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

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