Finite-state automata are a central computational model in computer science, with numerous and diverse applications. In one such application, viz. model-checking, automata over infinite words play a central rˆole. In this thesis, we concentrate on B¨uchi automata (BA), which are arguably the simplest finite-state model recognizing languages of infinite words. Two algorithmic problems are paramount in the theory of automata: language inclusion and automata minimization. They are both PSPACE-complete, thus under standard complexity-theoretic assumptions no deterministic algorithm with worst case polynomial time can be expected. In this thesis, we develop techniques to tackle these problems. In automata minimization, one seeks the smallest automaton recognizing a given language (“small” means with few states). Despite PSPACE-hardness of minimization, the size of an automaton can often be reduced substantially by means of quotienting. In quotienting, states deemed equivalent according to a given equivalence are merged together; if this merging operation preserves the language, then the equivalence is said to be Good for Quotienting (GFQ). In general, quotienting cannot achieve exact minimization, but, in practice, it can still offer a very good reduction in size. The central topic of this thesis is the design of GFQ equivalences for B¨uchi automata. A particularly successful approach to the design of GFQ equivalences is based on simulation relations. Simulation relations are a powerful tool to compare the local behavior of automata. The main contribution of this thesis is to generalize simulations, by relaxing locality in three perpendicular ways: by fixing the input word in advance (fixed-word simulations, Ch. 3), by allowing jumps (jumping simulations, Ch. 4), and by using multiple pebbles (multipebble simulations for alternating BA, Ch. 5). In each case, we show that our generalized simulations induce GFQ equivalences. For fixed-word simulation, we argue that it is the coarsest GFQ simulation implying language inclusion, by showing that it subsumes a natural hierarchy of GFQ multipebble simulations. From a theoretical perspective, our study significantly extends the theory of simulations for BA; relaxing locality is a general principle, and it may find useful applications outside automata theory. From a practical perspective, we obtain GFQ equivalences coarser than previously possible. This yields smaller quotient automata, which is beneficial in applications. Finally, we show how simulation relations have recently been applied to significantly optimize exact (exponential) language inclusion algorithms (Ch. 6), thus extending their practical applicability.

La thèse s'inscrit dans le cadre du projet européen VENUS. Dans ce contexte, la photogrammétrie est utilisée pour produire des relevés 3D sur les objets. La connaissance sur ces objets provient à la fois de l'archéologie sous-marine et de la photogrammétrie. Les informations étant structurées, hiérarchisées et parfois incomparables, nous nous sommes intéressés aux bases de croyance partiellement préordonnées. Par ailleurs, l'acquisition des données peut conduire à l'apparition d'incohérence. Nous avons étendu l'approche des R-ensembles à la restauration de la cohérence. Nous avons également proposé un cadre de travail pour la révision de bases de croyance partiellement préordonnées et deux relations d'inférence lexicograhique. nous avons fourni pour ces approches une mise en oeuvre en utilisant la programmation logique avec ASP. Finalement, nous avons implanté notre méthode de restauration de la cohérence dans le contexte de VENUS et nous l'avons testé sur les relevés issus du projet. / This PHD has been performed within the European VENUS project. In this context, photogrammetry is used to produced 3D survey on objects and the knowledge on studied artefacts comes from both underwater archaeology and photogrammetry. This information being structured, hierachized and sometimes incomparable, we focused on partially preordered belief bases. Data acquisition possibly leads to inconsistency. We extended the Removed Set approach to inconsistency handling. To compare subsets of formulae to remove in order to restore consistency, we introduced the lexicographic comparator. Moreover, we proposed a new framework for the revision of partially preordered belief bases and two lexicographic inference relations. We proposed an implementation stemming from ASP. Finally, we implemented our inconsistency handling method in the VENUS context and we provided an experimental study on 3D surveys of the project.

Nondeterministic finite automaton is an important tool, which is used to process strings in many different areas of programming. It is important to try to reduce its size for increasing programs' effectiveness. However, this problem is computationally hard, so we need to search for new techniques. Basics of finite automata are described in this work. Some methods for their reduction are then introduced. Usable reduction algorithms are described in greater detail. Then they are implemented and tested. The test results are finally evaluated.