Some Contributions to the Algebraic Theory of Automata
Loading...
Identifiers
Publication date
2015
Reading date
22-10-2015
Authors
Advisors
Ballester-Bolinches, Adolfo
Pin, Jean-Éric
Journal Title
Journal ISSN
Volume Title
Publisher
Metrics
Export
Abstract
En el present treball estudiarem els autòmats des d'una perspectiva tant algebraica com coalgebraica.
Volem aprofitar la natura dual d'aquests objectes per a presentar un marc unificador que explique i
estenga alguns resultats recents de la teoria d'autòmats. Per tant, la secció 2 conté nocions i definicions
preliminars per a mantenir el treball tan contingut com siga possible. Així, presentarem les nocions
d'àlgebra i coàlgebra per a un endofunctor. També introduirem alguns conceptes sobre monoides i llenguatges.
En aquest capítol també exposarem les nocions d'autòmats deterministes i no deterministes, homomorfismes
i bisimulacions d'autòmats i productes i coproductes d'aquestes estructures. Finalment, recordarem
algunes nocions bàsiques de teoria de reticles.
Des d'una perspectiva algebraica, els autòmats són àlgebres amb operacions unàries. En aquest context, una
equació és simplement un parell de paraules. Direm que una equació és satisfeta per un autòmat si per a
cada estat inicial possible els estats als quals s'arriba des de l'estat considerat sota l'acció de les
dues paraules coincideix. Es pot provar que, per a un autòmat donat, podem construir el major conjunt
d'equacions que aquest satisfà. Aquest conjunt d'equacions resulta ser una congruència en el monoide lliure
associat a l'alfabet d'entrada i ens permet definir l'autòmat lliure, denotat per free.
Pel que respecta a la perspectiva coalgebraica, un autòmat és un sistema de transicions amb estats finals.
Així, una coequació és un conjunt de llenguatges. Direm que una coequació és satisfeta per un autòmat, si
per a cada observació possible (coloracions sobre els estats indicant-ne la finalitat o no), el llenguatge
acceptat per l'autòmat es troba dins la coequació considerada. Intuïtivament, les coequacions poden ser
pensades com comportaments o especificacions en el disseny que se suposa que una coàlgebra deu tindre.
Com hem fet abans, per a un autòmat donat, podem construir el menor conjunt de coequacions que aquest satisfà.
Aquest conjunt de coequacions resulta ser un subconjunt amb característiques ben determinades del conjunt de
tots els llenguatges associats a l'alfabet d'entrada i ens permet definir l'autòmat colliure, denotat per
cofree. Provem, a més, que aquestes construccions basades en equacions i coequacions són functorials.
Al capítol 3 hem establert un nou resultat que presenta la dualitat entre quocients de congruència del
monoide lliure i el seu conjunt de coequacions, que són àlgebres booleanes completes i atòmiques tancades
sota derivació i que hem anomenat preformacions de llenguatges. Aquesta dualitat no imposa cap restricció
en la grandària dels objectes, per tant, també s'aplica a objectes infinits.
El capítol 3 està basat en els següents articles:
- 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.
Aquesta dualitat és emprada en el capítol 4 per a presentar un nou apropament al teorema de varietats
d'Eilenberg. En primer lloc presentem una descripció equivalent, basada en equacions i coequacions, de
la noció original de varietat de llenguatges d'Eilenberg. Aquesta nova descripció és un dels millors
exemples possibles del poder expressiu del functors free i cofree.
Una adaptació adient d'aquestes construccions permet presentar un resultat de tipus Eilenberg per
a formacions de monoides no necessàriament finits. En el nostre cas, primerament provem que les
formacions de monoides estan en correspondència biunívoca amb les formacions de congruències.
Un segon pas en la prova relaciona formacions de congruències amb formacions de llenguatges.
Així, provem que tots tres conceptes són equivalents
Formacions de monoides -- Formacions de congruències -- Formacions de llenguatges
La primera correspondència pareix ser completament nova i relaciona formacions de monoides
amb filtres de congruències per a cada monoide. L'última correspondència és un dels millors exemples
on poder aplicar la dualitat presentada al capítol 3. A més, donem una aplicació d'aquestes equivalències
per al cas dels llenguatges relativament disjuntius. Aquests teoremes poden ser adequadament modificats per a
cobrir el cas de les varietats de monoides en el sentit de Birkhoff. Discutim aquest cas particular al final del capítol 4.
Els resultats d'aquest capítol han estat enviats per a la seua possible publicació en una revista científica sota el títol
- A. Ballester-Bolinches, E. Cosme-Llópez, R. Esteban-Romero, and J. Rutten. Formations of monoids, congruences, and formal languages. 2015.
El capítol 5 està completament dedicat a l'estudi de l'objecte final associat als autòmats no deterministes. En general,
les tècniques emprades en el capítol 5 difereixen de les presentades en els capítols 3 i 4. En conseqüència,
al principi d'aquest capítol introduïm alguns conceptes preliminars sobre bisimulacions i objectes finals. E
l nostre resultat principal és presentat en el Teorema 5.17, que descriu l'autòmat final no determinista amb
l'ajuda d'estructures basades en llenguatges.
A continuació, relacionem altres descripcions de l'autòmat final no determinista amb la nostra construcció.
El capítol 5 està basat en el següent article:
- 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.
Certament, els diferents punts de vista emprats en aquesta dissertació ja han estat explorats en
alguns altres treballs. Per això, al final de cada capítol presentem un estudi detallat dels treballs
relacionats i discutim les aportacions o millores realitzades en els resultats existents.
Finalment, el capítol 6
presenta les conclusions i indica els treballs que caldrà
realitzar en el futur. També presentem alguns del articles de recerca que es deriven de la realització d'aquest projecte.