Automates à contraintes semilinéaires = Automata with a semilinear constraint
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.
Automata Parikh automata Semilinear sets Affine functions Decidability Bounded languages Regular languages Typed monoids Rational series Model-checking Model-checking