Automates à contraintes semilinéaires = Automata with a semilinear constraint
Thèse ou mémoire / Thesis or Dissertation
Date de publication
Autrices et auteurs
Identifiant ORCID de l’auteur
Contributrices et contributeurs
Direction de recherche
Publié dans
Date de la Conférence
Lieu de la Conférence
Éditeur
Cycle d'études
Doctorat / Doctoral
Programme
Affiliation
Mots-clés
- Automates
- Automata
- Langages bornés
- Bounded languages
- Langages réguliers
- Regular languages
- Monoïdes typés
- Typed monoids
- Series rationnelles
- Rational series
- Model-checking
- Model-checking
- Automates de Parikh
- Parikh automata
- Ensembles semilinéaires
- Semilinear sets
- Fonctions affines
- Affine functions
- Decidabilité
- Decidability
Organisme subventionnaire
Résumé
Résumé
Cette thèse présente une étude dans divers domaines de l'informatique
théorique de modèles de calculs combinant automates finis et contraintes
arithmétiques. Nous nous intéressons aux questions de décidabilité,
d'expressivité et de clôture, tout en ouvrant l'étude à la complexité, la
logique, l'algèbre et aux applications. Cette étude est présentée au travers
de quatre articles de recherche.
Le premier article, Affine Parikh Automata, poursuit l'étude de Klaedtke et Ruess
des automates de Parikh et en définit des généralisations et restrictions.
L'automate de Parikh est un point de départ de cette thèse; nous montrons que
ce modèle de calcul est équivalent à l'automate contraint que nous
définissons comme un automate qui n'accepte un mot que si le nombre de fois
que chaque transition est empruntée répond à une contrainte arithmétique.
Ce modèle est naturellement étendu à l'automate de Parikh affine qui
effectue une opération affine sur un ensemble de registres lors du
franchissement d'une transition. Nous étudions aussi l'automate de
Parikh sur lettres: un automate qui n'accepte un mot que si le nombre de
fois que chaque lettre y apparaît répond à une contrainte arithmétique.
Le deuxième article, Bounded Parikh Automata, étudie les langages
bornés des automates de Parikh. Un langage est borné s'il existe des
mots w_1, w_2, ..., w_k tels que chaque mot du langage peut s'écrire
w_1...w_1w_2...w_2...w_k...w_k. Ces langages sont
importants dans des domaines applicatifs et présentent usuellement de bonnes
propriétés théoriques. Nous montrons que dans le contexte des langages
bornés, le déterminisme n'influence pas l'expressivité des automates de
Parikh.
Le troisième article, Unambiguous Constrained Automata, introduit les
automates contraints non ambigus, c'est-à-dire pour lesquels il
n'existe qu'un chemin acceptant par mot reconnu par l'automate. Nous
montrons qu'il s'agit d'un modèle combinant une meilleure expressivité et de
meilleures propriétés de clôture que l'automate contraint déterministe. Le
problème de déterminer si le langage d'un automate contraint non ambigu est
régulier est montré décidable.
Le quatrième article, Algebra and Complexity Meet Contrained Automata,
présente une étude des représentations algébriques qu'admettent les automates
contraints et les automates de Parikh affines. Nous déduisons de ces
caractérisations des résultats d'expressivité et de complexité. Nous
montrons aussi que certaines hypothèses classiques en complexité
computationelle sont reliées à des résultats de séparation et de non clôture
dans les automates de Parikh affines.
La thèse est conclue par une ouverture à un possible approfondissement, au
travers d'un certain nombre de problèmes ouverts.
This thesis presents a study from the theoretical computer science perspective of computing models combining finite automata and arithmetic constraints. We focus on decidability questions, expressiveness, and closure properties, while opening the study to complexity, logic, algebra, and applications. This thesis is presented through four research articles. The first article, Affine Parikh Automata, continues the study of Klaedtke and Ruess on Parikh automata and defines generalizations and restrictions of this model. The Parikh automaton is one of the starting points of this thesis. We show that this model of computation is equivalent to the constrained automaton that we define as an automaton which accepts a word only if the number of times each transition is taken satisfies a given arithmetic constraint. This model is naturally extended to affine Parikh automata, in which an affine transformation is applied to a set of registers on taking a transition. We also study the Parikh automaton on letters, that is, an automaton which accepts a word only if the number of times each letter appears in the word verifies an arithmetic constraint. The second article, Bounded Parikh Automata, focuses on the bounded languages of Parikh automata. A language is bounded if there are words w_1, w_2, ..., w_k such that every word in the language can be written as w_1...w_1w_2...w_2 ... w_k...w_k. These languages are important in applications and usually display good theoretical properties. We show that, over the bounded languages, determinism does not influence the expressiveness of Parikh automata. The third article, Unambiguous Constrained Automata, introduces the concept of unambiguity in constrained automata. An automaton is unambiguous if there is only one accepting path per word of its language. We show that the unambiguous constrained automaton is an appealing model of computation which combines a better expressiveness and better closure properties than the deterministic constrained automaton. We show that it is decidable whether the language of an unambiguous constrained automaton is regular. The fourth article, Algebra and Complexity Meet Constrained Automata, presents a study of algebraic representations of constrained automata and affine Parikh automata. We deduce expressiveness and complexity results from these characterizations. We also study how classical computational complexity hypotheses help in showing separations and nonclosure properties in affine Parikh automata. The thesis is concluded by a presentation of possible future avenues of research, through several open problems.
This thesis presents a study from the theoretical computer science perspective of computing models combining finite automata and arithmetic constraints. We focus on decidability questions, expressiveness, and closure properties, while opening the study to complexity, logic, algebra, and applications. This thesis is presented through four research articles. The first article, Affine Parikh Automata, continues the study of Klaedtke and Ruess on Parikh automata and defines generalizations and restrictions of this model. The Parikh automaton is one of the starting points of this thesis. We show that this model of computation is equivalent to the constrained automaton that we define as an automaton which accepts a word only if the number of times each transition is taken satisfies a given arithmetic constraint. This model is naturally extended to affine Parikh automata, in which an affine transformation is applied to a set of registers on taking a transition. We also study the Parikh automaton on letters, that is, an automaton which accepts a word only if the number of times each letter appears in the word verifies an arithmetic constraint. The second article, Bounded Parikh Automata, focuses on the bounded languages of Parikh automata. A language is bounded if there are words w_1, w_2, ..., w_k such that every word in the language can be written as w_1...w_1w_2...w_2 ... w_k...w_k. These languages are important in applications and usually display good theoretical properties. We show that, over the bounded languages, determinism does not influence the expressiveness of Parikh automata. The third article, Unambiguous Constrained Automata, introduces the concept of unambiguity in constrained automata. An automaton is unambiguous if there is only one accepting path per word of its language. We show that the unambiguous constrained automaton is an appealing model of computation which combines a better expressiveness and better closure properties than the deterministic constrained automaton. We show that it is decidable whether the language of an unambiguous constrained automaton is regular. The fourth article, Algebra and Complexity Meet Constrained Automata, presents a study of algebraic representations of constrained automata and affine Parikh automata. We deduce expressiveness and complexity results from these characterizations. We also study how classical computational complexity hypotheses help in showing separations and nonclosure properties in affine Parikh automata. The thesis is concluded by a presentation of possible future avenues of research, through several open problems.
Table des matières
Notes
Notes
Autre version linguistique
Ensemble de données lié
Licence
Approbation
Évaluation
Complété par
Référencé par
Ce document diffusé sur Papyrus est la propriété exclusive des titulaires des droits d'auteur et est protégé par la Loi sur le droit d'auteur (L.R.C. (1985), ch. C-42). Sauf si le document est diffusé sous une licence Creative Commons, il ne peut être utilisé que dans le cadre d'une utilisation équitable et non commerciale comme le prévoit la Loi (i.e. à des fins d'étude privée ou de recherche, de critique ou de compte-rendu). Pour toute autre utilisation, une autorisation écrite des titulaires des droits d'auteur sera nécessaire.