- -

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

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

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

Show simple item record

Files in this item

dc.contributor.author Ballester-Bolinches, A. es_ES
dc.contributor.author Cosme-Llopez, E es_ES
dc.contributor.author Esteban Romero, Ramón es_ES
dc.date.accessioned 2015-06-01T10:50:39Z
dc.date.available 2015-06-01T10:50:39Z
dc.date.issued 2014-05-29
dc.identifier.issn 0304-3975
dc.identifier.uri http://hdl.handle.net/10251/51041
dc.description.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. (C) 2014 Elsevier B.V. All rights reserved. es_ES
dc.description.sponsorship This work has been supported by the grant MTM2010-19938-C03-01 from the Ministerio de Ciencia e Innovacion (Spanish Government). The first author has been supported by a research project from the National Natural Science Foundation of China (NSFC, No. 11271085). The second author has been supported by the predoctoral grant AP2010-2764 from the Ministerio de Educacion (Spanish Government). We also thank Jean-Eric Pin and Jan Rutten for their helpful comments. Finally, we are indebted to the anonymous referees for their careful reading of the paper and for bringing to our attention some references we had missed. Their suggestions have helped us to improve the presentation of the paper. en_EN
dc.language Inglés es_ES
dc.publisher Elsevier es_ES
dc.relation Ministerio de Ciencia e Innovacion (Spanish Government) [MTM2010-19938-C03-01] es_ES
dc.relation National Natural Science Foundation of China (NSFC) [11271085] es_ES
dc.relation Ministerio de Educacion (Spanish Government) [AP2010-2764] es_ES
dc.relation.ispartof Theoretical Computer Science es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Non-deterministic automaton es_ES
dc.subject Formal language es_ES
dc.subject Coalgebra es_ES
dc.subject Bisimilarity es_ES
dc.subject Final automaton es_ES
dc.subject.classification MATEMATICA APLICADA es_ES
dc.title A description based on languages of the final non-deterministic automaton es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1016/j.tcs.2014.01.018
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Matemática Aplicada - Departament de Matemàtica Aplicada es_ES
dc.description.bibliographicCitation Ballester-Bolinches, A.; Cosme-Llopez, E.; Esteban Romero, R. (2014). A description based on languages of the final non-deterministic automaton. Theoretical Computer Science. 536:1-20. doi:10.1016/j.tcs.2014.01.018 es_ES
dc.description.accrualMethod Senia es_ES
dc.relation.publisherversion http://dx.doi.org/10.1016/j.tcs.2014.01.018 es_ES
dc.description.upvformatpinicio 1 es_ES
dc.description.upvformatpfin 20 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 536 es_ES
dc.relation.senia 255530


This item appears in the following Collection(s)

Show simple item record