Some contributions to the algebraic theory of automata

• Autores: Enric Cosme i Llópez
• Directores de la Tesis: Adolfo Ballester-Bolinches (dir. tes.) , Jean-Éric Pin (dir. tes.)
• Lectura: En la Universitat de València ( España ) en 2015
• Idioma: inglés
• Número de páginas: 111
• Tribunal Calificador de la Tesis: Francisco Pérez Monasor (presid.) , Alexandra Silva (secret.) , JAN RUTTEN (voc.)
• Enlaces
  • Tesis en acceso abierto en: RODERIC
• Resumen

  • In the present work we want to study automata both from an algebraic perspective and a coalgebraic one. We want to exploit the dual nature of these objects and present a unifying framework to explain and extend some recent results in automata theory.

    Accordingly, Section 2 contains background material and definitions to keep the work as self-contained as possible. Thus, the notions of algebra and coalgebra for endofunctors are presented. We also introduce some basic concepts on monoids and languages. In this Chapter we also introduce the notions of deterministic and non-deterministic automata, homomorphisms and bisimulations of automata and the product and coproduct of these structures. Finally, we recall some basic notions of lattice theory.

    From the algebraic perspective, automata are algebras with unary operations. In this context, an equation is just a pair of words, and it holds in an automaton if for every initial state, the states reached from that state by both words are the same. It can be shown that, for a given automaton, we can construct the largest set of equations it satifies, which turns out to be a congruence on the free monoid on the input alphabet. We use this construction to define the free automaton associated to a given automaton, denoted by free. Coalgebraically, an automaton is a transition system with final states. A coequation is then a set of languages and it is satisfied by an automaton if, for every possible observation (colouring the states as either final or not) the language accepted by the automaton is within the specified coequation. Intuitively, coequations can be thought of as behaviours, or pattern specifications that a coalgebra is supposed to have. As we did before, for a given automaton, we can construct the smallest set of coequations it satifies, which turns out to be a special subset on the set of all languages over the input alphabet. We use this construction to define the cofree automaton associated to a given automaton, denoted by cofree. These constructions based on equations and coequations are proved to be functorial.

    In Chapter 3 we have established a new duality result between congruence quotients of the free monoid and its set of coequations, what we called preformations of languages, which are complete atomic boolean algebras closed under derivatives. This duality result does not impose any restriction on the size of the objects, therefore infinite objects are allowed. Chapter 3 is based on the following papers:

    J.J.M.M. Rutten, A. Ballester-Bolinches, and E. Cosme-Llópez. Varieties and covarieties of languages (preliminary version). In D. Kozen and M. Mislove, editors, Proceedings of MFPS XXIX, volume 298 of Electron. Notes Theor. Comput. Sci., pages 7-28, 2013.

    A. Ballester-Bolinches, E. Cosme-Llópez, and J. Rutten. The dual equivalence of equations and coequations for automata. Information and Computation, 244:49-75, 2015.

    This duality result is used in Chapter 4 to present a renewed approach to Eilenberg¿s variety theorem. In the first place, we introduce an equivalent description based on equations and coequations of the original notion of variety of regular language, originally introduced by Eilenberg. This description is one of the best examples of the expressiveness power of the aforementioned functors free and cofree. A suitable adaptation of this construction allows us to present an Eilenberg-like result for formations of (non-necessarily finite) monoids. In our case, we first prove that formations of monoids are in one-to-one correspondence with formations of congruences. A second step in our proof relates formations of congruences and formations of languages. All in all, these three concepts are shown to be equivalent Formations of monoids - Formations of congruences - Formations of languages The first correspondence seems to be completely new and relates formations of monoids to filters of congruences on every possible free monoid. The last correspondence is one of the best possible examples of application of the duality theorem presented in Chapter 3. We also give an application of this equivalence to the case of relatively disjunctive languages. These theorems can be slightly adapted to cover the case of varieties of monoids in the sense of Birkhoff. We discuss this particular case at the end of the Chapter 4. The results of this Chapter have been submitted to a journal for its possible publication under the title A. Ballester-Bolinches, E. Cosme-Llópez, R. Esteban-Romero, and J. Rutten. Formations of monoids, congruences, and formal languages. 2015. Submitted.

    Chapter 5 is completely devoted to the study of the final object associated to non-deterministic automata. In general, the techniques applied in Chapter 5 differ from those presented in Chapters 3 and 4. Consequently, at the beginning of this chapter we introduce some basic background on bisimulations and final objects. Our main result is presented in Theorem 5.17 which describes the final non-deterministic automaton with the help of structures based on languages. Hereafter, we relate other descriptions of the final non-deterministic automaton with our construction. Chapter 5 is based on the following paper:

    A. Ballester-Bolinches, E. Cosme-Llópez, and R. Esteban-Romero. A description based on languages of the final non-deterministic automaton. Theor. Comput. Sci., 536(0):1-20, 2014.

    Certainly, the point of view that we adopt throughout this work has been explored in some other references too. Therefore, at the end of each Chapter, we present a detailed study of the related work and how our work subsumes or improves the existing results. Finally, Chapter 6 sets out the conclusions and indicates future work. We also present some of the derived research papers we have made during the realisation of this project.