Cette thèse traite des langages reconnaissables de mots indexés par des ordinaux.<br /><br />Plusieurs classes d'automates qui reconnaissent de tels mots ont été introduites par Büchi. Elles diffèrent par la longueur des mots reconnus par les automates. Nous en utilisons quatre: la classe pour les mots de longueur [$\omega$] , celle pour les mots de longueur inférieure à [$\omega^(n+1)$] , où n est un entier naturel, celle pour les mots de longueur dénombrable, et celle pour les mots de longueur quelconque. Nous y ajoutons la classe des automates de Kleene traditionnelle, sur les mots finis. Nous remontrons que ces différentes définitions d'automates sont équivalentes, c'est-à-dire que données deux de ces classes et un automate d'une des deux, la restriction du langage reconnu par l'automate aux mots du domaine le plus petit des deux classes est la restriction du langage reconnu par un automate de l'autre classe au même domaine. Nous donnons également une présentation unifiée de la déterminisation pour chacune des classes qui reconnaît au plus des mots de longueur dénombrable.<br /><br />Les semigroupes finis sont un formalisme équivalent aux automates pour définir des ensembles de mots finis. Perrin, Pin et Wilke ont introduits des structures algébriques adaptées à l'étude des langages de mots de longueur [$\omega$] , qui, quand elles sont finies, sont équivalentes aux automates. Nous généralisons l'approche algébrique de la théorie des langages reconnaissables de mots de longueur [$\omega$] aux mots de longueur inférieure à [$\omega^(n+1)$] , puis aux mots de longueur dénombrable. Pour cela, nous définissons deux structures algébriques, les [$\omega^n$] -semigroupes et les [$\omega_1$] -semigroupes, qui, quand elles sont finies, sont équivalentes respectivement aux automates pour les mots de longueur inférieure à [$\omega^(n+1)$] et aux automates pour les mots de longueur dénombrable. Comme pour le cas des mots de longueur [$\omega$] , une algèbre syntaxique peut être canoniquement associée à chaque langage reconnaissable. Nous définissons le produit de Schützenberger et le produit en couronne sur les [$\omega_1$] -semigroupes. Nous étendons également le théorème des variétés d'Eilenberg aux mots de longueur dénombrable.<br /><br />Finalement, nous remontrons l'équivalence entre langages reconnus par automates et langages définis par énoncés de logique monadique du second ordre quand on s'intéresse aux mots de longueur dénombrable. Le théorème d'équivalence de Schützenberger entre langages sans étoile et semigroupes finis apériodiques est étendu aux mots de longueur inférieure à [$\omega^(n+1)$] , et le théorème d'équivalence entre langages sans étoile et langages définis par énoncés de logique du premier ordre de l'ordre linéaire de McNaughton et Papert est étendu aux mots de longueur quelconque.

Th. doct.-ing.--Lille 1, 1979. N°: 229.

Cette thèse porte sur la génération aléatoire uniforme des automates finis et l'analyse des algorithmes de minimisation qui s'y appliquent. La génération aléatoire permet de conduire une étude expérimentale sur les propriétésde l'objet engendré et sur les méthodes algorithmiques qui s'y appliquent. Il s'agit également d'un outil de recherche, qui permet de faciliter l'étude théorique du comportement moyen des algorithmes. L'analyse en moyenne des algorithmes s'inscrit dans la suite des travaux précurseurs de Donald Knuth. Le schéma classique en analyse d'algorithmes consiste à étudier le pire des cas, qui n'est souvent pas représentatif du comportement de l'algorithme en pratique. D'un point de vue théorique, on définit ce qui se produit "souvent'' en fixant une loi de probabilitésur les entrées de l'algorithme. L'analyse en moyenne consiste alors à estimer des ressources utiliséespour cette distribution de probabilité. Dans ce cadre, j'ai travaillé sur des algorithmes de génération aléatoire d'automatesdéterministes accessibles (complets ou non). Ces algorithmes sont basés sur de la combinatoirebijective, qui permet d'utiliser un procédé générique : les générateurs de Boltzmann. J'ai ensuite implanté ces méthodes dans deux logiciels : REGAL et PREGA. Je me suis intéressé à l'analyse en moyenne des algorithmes de minimisation d'automateset j'ai obtenu des résultats qui montrent le cas moyen des algorithmes de Moore et Hopcroft est bien meilleur que le pire des cas / This thesis is about the uniform random generation of finite automata and the analysisof their state minimization algorithms. Random generators allow to conduct an experimental study on the properties of the generated objectand on the algorithms that apply to this object. It is also a useful tool for research that facilitates the theoretical study of the average behavior of algorithms. Usually, the analysis of an algorithm focuses on the worst case scenario, which is often not representative of thepractical behavior of the algorithm. From a theoretical point of view, one can define what happens "often" by fixing a probability law on the algorithm's inputs. The average analysis consists in the estimation ofthe requested resources, according to this probability distribution.In this context, I worked on several algorithms for the random generation of deterministic accessibleautomata (complete or not).Those algorithms are based on bijective combinatorics, that allows to use generic tools called the Boltzmann generators. I implemented those methods in two softwares : REGAL and PREGA. I studied the average complexity of state minimization algorithms and obtained results showing that theaverage case of the two algorithms due to Moore and Hopcroft is way better than the worst case

Dans le cadre de ce sujet de thèse, on s'intéresse à la surveillance des systèmes hybrides à forte dynamique événementielle. L'objectif est de détecter les défauts permanents et intermittents qui causent l'accélération et le ralentissement des tâches des systèmes. C'est dans ce contexte que se situent les principales contributions suivantes des travaux consignés dans la présente thèse : - Le développement d'une méthode de surveillance des processus basée sur les automates hybrides linéaires (AHL). Cette méthode consiste en premier lieu à l'établissement du modèle AHL du système dynamique en tenant compte des contraintes physiques et dynamiques de celui-ci. - La réalisation d'une analyse d'atteignabilité qui consiste à définir toutes les trajectoires pouvant amener le système à son objectif tout en respectant le cahier des charges qui lui est imposé. L'extension de l'approche en utilisant les automates hybrides rectangulaires. Cette sous-classe d'automates nous a permis de modéliser des systèmes plus complexes donc une modélisation hybride riche et a permis également une analyse formelle. Cette partie a été ponctuée par l'implémentation du système de surveillance qui consiste à déterminer les équations caractérisant chaque sommet de l'automate qui modélise le système. / As part of this thesis, we focus on the monitoring of hybrid systems with high dynamic event. The aim is to detect faults that cause permanent and intermittent acceleration and deceleration systems tasks. It is in this context that the following are the main contributions of the work reported in this thesis: - The development of a method for process monitoring based on linear hybrid automata (AHL). This method involves first the establishment of the AHL model the dynamic system taking into account the physical and dynamic one. - The realization of a reachability analysis of defining all paths that can cause the system to its target while respecting the specifications imposed on it. The extension of the approach using the rectangular hybrid automata. This class of controllers has allowed us to model more complex systems, therefore, a hybrid modeling rich and also allowed a formal analysis. This part was punctuated by the implementation of the monitoring system by determining equations characterizing each summit of the automaton that models the system.

Context. GUI-based automation testing is a costly and tedious activity in practice. As GUIs are well-known for being modified and redesigned throughout the development process, the corresponding test scripts are not valid anymore thereby being a hindrance to automation. Hence, substantial effort is invested in maintaining GUI test scripts which often leads to rework or waste due to improper decisions. As a result, practitioners have identified the need for decision support regarding when should GUI automation testing begin and how to make it easier and also identify what are the factors leading to waste in GUI-based automation testing. The current literature provides solutions relating to automation in general and few answers for GUI based-automation testing. Such generic answers might not be applicable to GUI test automation and also industries new to GUI development and testing. Thus, it is necessary to validate if the general solutions are applicable to GUI test automation and find additional answers that are not identified previously from practitioners opinions in an industrial context. Objectives. Capture relevant information regarding the current approach for GUI test automation within the subsystems from a case company. Next, identify the criteria for when to begin automation, testability requirements and factors associated with waste from literature and practice. Methods. We conducted a multiple-case study to explore opinions of practitioners in two subsystems at a Swedish telecommunication industry implementing GUI-automation testing. We conducted a literature review to identify answers from scientific literature prior to performing a case study.A two-phased interview was performed with different employees to collect their subjective opinions and also gather their opinions on the evidence collected from the literature. Later, Bayesian synthesis method was used to combine subjective opinions of practitioners with research-based evidence to produce context-specific results. Results. We identified 12 criteria for when to begin automation, 16 testability requirements and 15 factors associated with waste in GUI test automation.Each of them is classified into categories namely SUT-related,test-process related, test-tool related, human and organizational, environment and cross-cutting. New answers which were not present in the existing literature in the domain of the research are found. Conclusions. On validating the answers found in literature, it was revealed that the answers applicable for software test automation, in general, are valid for GUI automation testing as well. Since we incorporated subjective opinions to produce context specific results, we gained an understanding that every practitioner has their own way of working. Hence, this study aids in developing a common understanding to support informed subjective decisions based on evidence.

Le séchage des dispersions colloïdales a été et demeure très étudié en raison de son extrême complexité et de son utilisation dans de nombreuses applications. Dans cette thèse, nous avons développé une simulation, d'abord unidirectionnelle, basée sur le principe des automates cellulaires, qui traite la problématique du séchage horizontal et vertical. Ce travail permet de prédire, par calcul numérique, la distribution des particules et la position des fronts de séchage dans les dépôts de dispersions sous forme de films minces. Nos résultats ont montré que la pression existant dans le fluide est la somme des pressions de Laplace et hydrostatique. Par rapport aux modèles existants, cela modifie la convection des particules dans la partie fluide de la dispersion. La diffusion collective des particules chargées a été étudiée également. Contrairement aux prédictions théoriques antérieures, nous avons pu montrer que la diffusion collective des particules chargées pouvait jouer un rôle majeur, y compris dans le cadre de l’approximation de lubrification. Finalement, la simulation 1D a été étendue en 2D, ce qui a permis de comprendre la raison pour laquelle deux fronts dans deux directions perpendiculaire (cas d’une géométrie rectangulaire) avancent à des vitesses différentes. Une comparaison entre les données expérimentales et le calcul numérique sur le profil du film et la vitesse des fronts de séchage pour une dispersion de silice montre un bon accord. / Drying of colloidal dispersions, given their uses in several fields in everyday life, has been the subject of many studies for a long time. In this thesis, we first developed an unidirectional simulation, based on the principle of the cellular automaton, which deals with the problem of horizontal and vertical drying. This work makes it possible to predict, by numerical calculation, the distribution of the particles and the position of drying fronts in deposits in form of thin films.The profile of the film in the liquid part was studied. Our results have shown that the pressure in the fluid is the sum of the Laplace and hydrostatic pressures. This result affects the dynamics of particles in the fluid part of the dispersion, in particular convection. The collective diffusion of charged particles has also been studied. Contrary to what was predicted in previous theoretical models, we were able to show that the collective diffusion of the charged particles could be important even within the lubrication approximation. Finally, the 1D simulation was extended to 2D in order to understand the reason why two fronts in perpendicular directions (case of a rectangular geometry) advance at different speeds. A comparison between the experimental data for the drying of a silica dispersion and the numerical calculation shows good agreement.

La vérification en ligne de spécifications formelles permet de créer des détecteurs d'erreur dont le pouvoir de détection dépend en grande partie du formalisme vérifié à l'exécution. Plus le formalisme est puissant plus la séparation entre les exécutions correctes et erronées peut être précise. Cependant, l'utilisation des vérifieurs en-ligne dans le but de détecter des erreurs est entravée par deux problèmes récurrents : le coût à l'exécution de ces vérifications, et le flou entourant les propriétés sémantiques exactes des signaux d'erreur ainsi générés. L'objectif de cette thèse est de clarifier les conditions d'utilisation de tels détecteurs dans le cadre d'applications « temps réel » critiques. Dans ce but, nous avons donné l'interprétation formelle de la notion d'erreur comportementale « temps réel». Nous définissions la propriété de détection « au plus tôt » qui permet de d'identifier la classe des détecteurs qui optimisent la latence de détection. Pour illustrer cette classe de détecteurs, nous proposons un prototype qui vérifie un comportement décrit par un automate temporisé. La propriété de détection au plus tôt est atteinte en raisonnant sur l'abstraction temporelle de l'automate et non sur l'automate lui-même. Nos contributions se déclinent dans trois domaines, la formalisation de la détection au plus tôt, sa traduction pour la synthèse de détecteurs d'erreur à partir d'automate temporisés, puis le déploiement concret de ces détecteurs sur une plate-forme de développement temps réel, Xenomai. / Runtime verification of formal specifications provides the means to generate error detectors with detection capabilities depending mostly on the kind of formalism considered. The stronger the formalism is the easier the speration between correct and erroneous execution is. Nevertheless, two recurring issues have to be considered before using such error detection mechanisms. First, the cost, at run-time, of such error detector has to be assessed. Then, we have to ensure that the execution of such detectors has a well defined semantics. This thesis aims at better understanding the conditions of use of such detectors within critical real-time software application. Given formal behavioural specification, we defined the notion of "behavioural error". Then, we identify the class of early detectors that optimize the detection latency between the occurence of such errors and their signalling. The whole generation process has been implemented for specifications provided as timed automata. The prototype achieves early error detection thanks to a preprocessing of the automaton to generate its temporal abstraction. Our contributions are threefold : formalisation of early detection, algorithms for timed automata run-time verification, and prototyping of such detectors on a real-time kernel, Xenomai.

Dans cette thèse nous étudions le pouvoir d'expression de plusieurs logiques sur les arbres finis. En particulier, nous cherchons à obtenir une compréhension précise du pouvoir d'expression de la logique du premier ordre sur les arbres finis. Nous étudions un nombre important de logiques- pour cette raison nous procédons par comparaison avec une logique qui les contient et nous sert de référence: la logique monadique du second-ordre. Chaque logique que nous considérons est un fragment de la logique monadique du second ordre. MSO est liée à la théorie des langages formels. A chaque formule logique correspond un langage d'arbre: celui des arbres satisfaisant la formule. De plus, étant donné une logique nous pouvons lui associer une classe de langages d'arbres: la classe des langages définissables par une formule de cette logique. Dans le cadre des arbres finis, MSO correspond exactement à la classe des langages réguliers. Étant donné une logique, nous cherchons en fait à obtenir une caractérisation décidable de la classe de langages définissable par celle-ci. Par caractérisation décidable nous entendons un algorithme résolvant le problème suivant: pour un automate d'arbre finis, décider si le langage appartient à la classe en question. Nos caractérisations décidables sont en fait obtenue en exhibant pour chaque classe un ensemble de propriétés de clôture vérifiées par un langage si et seulement si celui-ci appartient à la classe en question. Nous montrons ensuite que chaque propriété de clôture est décidable. Énoncer et prouver de telles propriétés de clôture permet généralement d'obtenir une bonne compréhension du pouvoir de la logique correspondante. Le problème ouvert principal de ce domaine de recherche est l'obtention d'une caractérisation décidable pour la logique du premier ordre. Nous présentons des caractérisation décidables pour plusieurs fragment de FO. Nous commençons par la présentation de trois caractérisations décidable pour des classes de langages d'arbres de rang borné. La première classe que nous considérons est celle des langages définissables par la logique EF + F-1. Cette logique permet de naviguer dans l'arbre en se déplaçant soit vers un ancêtre, soit vers un descendant. La second classe est celle des arbres de rang borné définissables par la logique du premier ordre en n'utilisant qu'une seule alternance de quantificateurs. La dernière classe est celle des langages définissables par une combinaison booléenne de formules existentielles du premier ordre. Dans le cadre des forêts, nous étudions la classe des langages définissable par la logique du premier ordre à deux variables et deux prédicats correspondants respectivement à la relation ancêtre et la relation frère suivant. Nous présentons une caractérisation pour cette logique. La dernière classe pour laquelle nous présentons une caractérisation décidable est celle des langages localement testables (LT). UN langage est dans LT si l'appartenance d'un arbre à celui-ci ne dépends que des voisinages d'une certaine taille fixée dans l'arbre. / In this thesis we investigate the expressive power of several logics over finite trees. In particular we want to understand precisely the expressive power of first-order logic over finite trees. Because we study many logics, we proceed by comparison to a logic that subsumes them all and serves as a yardstick: monadic second-order logic. Each logic we consider is a fragment of monadic second-order logic. MSO is linked to the theory of formal languages. To each logical formula corresponds a tree language, which is the language of trees satisfying this formula. Furthermore, given a logic we can associate a class of tree languages: the class of languages definable by a formula of this logic. In the setting of finite trees MSO corresponds exactly to the class of regular tree languages. Given a logic, we actually look for a decidable characterization of the class of languages defined in this logic. By decidable characterization, we mean an algorithm for solving the following problem: given as input a finite tree automaton, decide if the recognized language belongs to the class in question. We will actually obtain our decidable characterizations by exhibiting for each class a set of closure properties such that a language is in the class under investigation if and only if it satisfies these closure properties. Each such closure property is then shown to be decidable. Stating and proving such closure properties usually yields a solid understanding of the expressive power of the corresponding logic. The main open problem in this research area is to obtain a decidable characterization for the class of tree languages that are definable in first-order logic. We provide decidable characterizations for several fragments of FO. First we provide three decidable characterizations for classes of regular languages of trees of bounded rank. The first class we consider is the class of languages definable in the temporal logic EF+F^-1. It essentially navigates the trees using two modalities for moving to a descendant node or an ancestor node. The second class we consider is the class of trees of bounded rank definable using one quantifier alternation. The last class, is the class of languages definable using a boolean combination of existential first order formulas. In the setting of forests, we investigate the class of languages definable in first-order logic using only two variables and two prediactes corresponding respectively to the ancestor and following sibling relations. We provide a characterization for this logic. The last class for which we provide a decidable characterization is the class of locally testable language (LT). A language L is in LT if membership in L depends only on the presence or absence of neighborhoods of a certain fixed size in the tree. We define notions of LT for both unranked trees and trees of bounded rank by adapting the definition of neighborhood to each setting. Then we provide a decidable characterization for both notions of LT.

Cette thèse se situe dans les domaines de la combinatoire algébrique, bijective et énumérative.Elle s'intéresse à l'étude des fonctions de parking généralisées suivant ces trois axes.medskip. Dans une première partie, on s'intéresse aux fonctions de parking généralisées en tant qu'espèce de structures combinatoires (théorie introduite par A.nom{Joyal} et développée F. nom{Bergeron}, G. nom{Labelle} et P.nom{Leroux}). On définit cette espèce à partir d'une équation fonctionnelle faisant intervenir l'espèce des séquences d'ensembles.On obtient un relèvement non-commutatif de la série indicatrice de cycles dans les fonctions symétriques non-commutatives, exprimé dans différentes bases.Par spécialisation, on obtient de nouvelles formules d'énumérations des fonctions de parking généralisées et de leurs types d'isomorphismes.En remplaçant l'espèce des ensembles par d'autres espèces dans l'équation fonctionnelle, on définit de nouvelles structures: les $seqPF$-tables de parking. Dans les cas particuliers où $seqPF : m mapsto a + b(m-1)$, on établit une bijection entre les $seqPF$-tables de parking et de nouvelles structures arborescentes, généralisant la bijection de C. H.nom{Yan} entre les $seqPF$-fonctions de parking et les séquences de $a$forêts de $b$-arbres.medskip. Dans une seconde partie, on s'intéresse à l'énumération d'automates. On commence par construire une bijection simple entre les automates(non-initiaux) et les séquences d'ensembles. À partir de cette bijection, on extrait la sous-famille des automates quasi-distingués (c'est-à-dire les automates pour lesquels les couples status de terminaison et fonction de transition des états sont distincts). L'énumération de ces automates quasi-distingués fournit une meilleure borne supérieure pour le nombre d'automates minimaux que celle obtenue par M.nom{Domaratzki} & textit{al}. Ensuite, on construit une nouvelle bijection entre les $2m^k$-fonctions de parking et les automates acycliques (non-initiaux) sur un alphabet à $k$ symboles. De cette dernière, on extrait, directement sur les fonctions parking, denombreuses informations de structure sur les automates, en particulier des informations liées à la minimalité.À partir de ces informations, on déduit une formule d'énumération des automates acycliques minimaux.medskipDans une troisième partie, on formalise la technique commune de réalisation polynomiale des algèbres de Hopf: fqsym, wqsym, pqsym, etc. Pour ceci, ondéfinit la notion de type d'alphabet et d'application partitionnante. La notion d'application partitionnante formalise les bonnes propriétés de la standardisation, le tassement, la parkisation, etc associées à ces précédentes algèbres de Hopf. On montre que certaines opérations, produit cartésien, coloration, union ouencore intersection, stabilisent ces notions.À partir de celles-ci, on définit deux constructions d'algèbres de Hopf combinatoire en dualité; et l'on montre qu'elles sont automatiquement munies de structures d'algèbres dendriformes et du produit $#$. En guise d'applications, on définit, pour toute famille de $seqPF$-fonctions deparking, une application généralisant la parkisation. On montre que cette dernière est une application partitionnante si et seulement si $seqPF : nmapsto 1 + m(n-1)$. Ceci permet de retrouver les algèbres de Hopf sur les$m$-fonctions de parking généralisées de J.-C. nom{Novelli} et J-.Y.nom{Thibon}. / This thesis comes within the scope of algebraic, bijective and enumerative combinatorics. It deals with the study of generalized parking functions following those axes.In the first part, we are interested in generalized parking as a species of combinatorial structures. We define this species from a functional equation involving the species of set sequences. We lift the cycle index serie to the non-commutative symmetric functions, express in several bases. By specialization, we obtain new enumeration formula of generalized parking and their isomorphism types.In the functional equation, the species of sets can be replaced by some other species. This defines new structures: the $chi$-parking tables. In particular cases with $chi : m mapsto a + b(m-1)$, we define a bijection between the $chi$-parking tables and new tree structures. This defines a generalization of the C. H. Yan bijection.In the second part, we are interested in the enumeration of automata. Firstly, we construct a simple bijection between (non-initial) automata and sequences of sets. From this bijection we extract a subfamily of quasi-distinguished automata. We obtain a better upper bound of the number of minimal automata than the one of M. Domaratzki.Then we construct a new bijection between $2m^k$-parking functions and (non-initial) acyclic automata over an alphabet of $k$ symbols. From this bijection we extract, from parking function, informations about automata structures. We deduce an enumeration formula of the minimal acyclic automata.In a third part, we formalize the common technique of polynomial realization of Hopf algebras: FQSym, WQSym, PQSym, etc.. We define a notion of type of alphabet and partitioning map. We highlight some operation which stabilizes these notions. Based on this, we define two constructions of dual combinatorial Hopf algebra; and we show that they are automatically endowed of dendriform coalgebra, and $#$-product.As an application, we define, for every family of $chi$-parking functions, a generalization of the parkization. We show that this is a partitionning map if and only if $chi : m mapsto 1 + b(m-1)$.

The aim of the thesis is to automate the process of loading data from particular distributors, make data quality management more transparent - consolidate data from particular distributors - mainly in the area of products and points of sale (pharmacies), process existing reports in modern reporting tool, which enables the creation of new reports, including graphically processed territorial data (map reports), with the possibility of interactive viewing of detailed data.