Paper “A description based on languages of the final non-deterministic automaton” published in Theoret. Comput. Sci.

The following paper has been published:

El siguiente artículo ha sido publicado:

El següent article ha sigut publicat:

A. Ballester-Bolinches, E. Cosme-Llópez, R. Esteban-Romero

A description based on languages of the final non-deterministic automaton

Theoret. Comput. Sci., 536 (2014), 1–20

http://dx.doi.org/10.1016/j.tcs.2014.01.018

Abstract

The study of the behaviour of non-deterministic automata has traditionally focused on the languages which can be associated to the different states. Under this interpretation, the different branches that can be taken at every step are ignored. However, we can also take into account the different decisions which can be made at every state, that is, the branches that can be taken, and these decisions might change the possible future behaviour. In this case, the behaviour of the automata can be described with the help of the concept of bisimilarity. This is the kind of description that is usually obtained when the automata are regarded as labelled transition systems or coalgebras.

Contrarily to what happens with deterministic automata, it is not possible to describe the behaviour up to bisimilarity of states of a non-deterministic automaton by considering just the languages associated to them. In this paper we present a description of a final object for the category of non-deterministic automata, regarded as labelled transition systems, with the help of some structures defined in terms of languages. As a consequence, we obtain a characterisation of bisimilarity of states of automata in terms of languages and a method to minimise non-deterministic automata with respect to bisimilarity of states. This confirms that languages can be considered as the natural objects to describe the behaviour of automata.

Keywords: Non-deterministic automaton; Formal language; Coalgebra; Bisimilarity; Final automaton

Paper “A description based on languages of the final non-deterministic automaton” accepted in Theoretical Computer Science

The paper “A description based on languages of the final non-deterministic automaton” has been accepted for publication in Theoretical Computer Science. The abstract can be found below. We will inform later about the publication details. It will be available on

http://dx.doi.org/10.1016/j.tcs.2014.01.018.

El artículo “A description based on languages of the final non-deterministic automaton” ha sido aceptado para su publicación en Theoretical Computer Science. El resumen aparece más abajo. Informaremos más adelante sobre los detalles bibliográficos. Estará disponible en

http://dx.doi.org/10.1016/j.tcs.2014.01.018.

L’article “A description based on languages of the final non-deterministic automaton” ha sigut acceptat per a la seua publicació en Theoretical Computer Science. El resum apareix davall. Informarem més endavant sobre els detalls bibliogràfics. Estarà disponible en

http://dx.doi.org/10.1016/j.tcs.2014.01.018.

Abstract: The study of the behaviour of non-deterministic automata has traditionally focused on the languages which can be associated to the different states. Under this interpretation, the different branches that can be taken at every step are ignored. However, we can also take into account the different decisions which can be made at every state, that is, the branches that can be taken, and these decisions might change the possible future behaviour. In this case, the behaviour of the automata can be described with the help of the concept of bisimilarity. This is the kind of description that is usually obtained when the automata are regarded as labelled transition systems or coalgebras.

Contrarily to what happens with deterministic automata, it is not possible to describe the behaviour up to bisimilarity of states of a non-deterministic automaton by considering just the languages associated to them. In this paper we present a description of a final object for the category of non-deterministic automata, regarded as labelled transition systems, with the help of some structures defined in terms of languages. As a consequence, we obtain a characterisation of bisimilarity of states of automata in terms of languages and a method to minimise non-deterministic automata with respect to bisimilarity of states. This
confirms that languages can be considered as the natural objects to describe the behaviour of automata.

Mathematics Subject Classification (2010): 68Q70, 68Q45, 68Q55, 18B20
Keywords: non-deterministic automaton, formal language, coalgebra, bisimilarity, final automaton.

Xarrada de divulgació professor Jean-Éric Pin/Charla de divulgación profesor Jean-Éric Pin

Nov ’13
7
13:00

CONFERÈNCIA DE DIVULGACIÓ

Lloc: Saló de graus Facultat de Ciències Matemàtiques

Dijous 7 de novembre, 13 hores

Títol: Todo lo que querías saber sobre autómatas y nunca te atreviste
a preguntar
Conferenciant: Jean-Éric Pin

Resum: En aquesta xarrada, adreçada a estudiants de grau i postgrau de
matemàtiques i informàtica, es presentarà una introducció a la teoria
d’autòmats i llenguatges formals. Aquesta teoria té la seua aplicació
en àmbits com el de la lingüística, el modelat, els analitzadors
lèxics, l’enginyeria automàtica, l’especificació i verificació formal
i la lògica, entre d’altres.

La xarrada serà impartida en anglès, acompanyada d’una presentació en
castellà.

Jean-Éric Pin és director de recerca del LIAFA (Laboratoire
d’Informatique Algorithmique: Fondements et Applications, unitat mixta
de recerca del CNRS i Université Paris Diderot, Paris 7). És expert en
teoria d’autòmats i de llenguatges formals, així com en semigrups i
topologia profinita. Les seues contribucions en aquestes àrees han
sigut molt destacades. És autor de diversos llibres d’investigació
(«Variétés de langages formels», «Semigroups, Algorithms, Automata and
Languages», «Infinite words», entre d’altres) i del programa «Semigroupe»
de càlcul amb semigrups. També és autor de 145 articles de recerca en
revistes científiques i actes de congressos. Ha dirigit 22 tesis
doctorals i ha sigut investigador principal de diversos projectes
internacionals de recerca. Recentment ha coŀlaborat amb Adolfo
Ballester Bolinches (Departament d’Àlgebra) i altres membres del seu
equip de recerca.

Més informació:
http://www.liafa.jussieu.fr/~jep/

 

CONFERENCIA DE DIVULGACIÓN

Salón de grados Facultat de Ciències Matemàtiques

Jueves 7 de noviembre, 13 horas
Título: Todo lo que querías saber sobre autómatas y nunca te atreviste
a preguntar
Conferenciante: Jean-Éric Pin

Resumen: En esta charla, dirigida a estudiantes de grado y posgrado de
matemáticas e informática, se presentará una introducción a la teoría
de autómatas y lenguajes formales. Esta teoría tiene su aplicación en
ámbitos como el de la lingüística, el modelado, los analizadores
léxicos, la ingeniería automática, la especificación y verificación
formal y la lógica, entre otros.

La charla será impartida en inglés, acompañada de una presentación en
castellano.

Jean-Éric Pin es director de investigación del LIAFA (Laboratoire
d’Informatique Algorithmique: Fondements et Applications, unidad mixta
de investigación del CNRS y Université Paris Diderot, Paris 7). Es
experto en teoría de autómatas y de lenguajes formales, así como en
semigrupos y topología profinita. Sus contribuciones en estas áreas
han sido muy destacadas. Es autor de varios libros de investigación
(«Variétés de langages formels», «Semigroups, Algorithms, Automata and
Languages», «Infinite words», entre otros) y del programa «Semigroupe»
de cálculo con semigrupos. También es autor de 145 artículos de
investigación en revistas científicas y actas de congresos. Ha
dirigido 22 tesis doctorales y ha sido investigador principal de
diversos proyectos internacionales de investigación. Recientemente ha
colaborado con Adolfo Ballester Bolinches (Departament d’Àlgebra) y
otros miembros de su equipo de investigación.

Más información:
http://www.liafa.jussieu.fr/~jep/