A description based on languages of the final non-deterministic automaton
NAGIOS: RODERIC FUNCIONANDO

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

DSpace Repository

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

Show simple item record

dc.contributor.author Ballester-Bolinches, Adolfo
dc.contributor.author Cosme i Llópez, Enric
dc.contributor.author Esteban Romero, Ramón
dc.date.accessioned 2015-11-12T11:41:20Z
dc.date.available 2015-11-12T11:41:20Z
dc.date.issued 2014
dc.identifier.uri http://hdl.handle.net/10550/48173
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.
dc.language.iso eng
dc.relation.ispartof Theoretical Computer Science, 2014, vol. 536, p. 1-20
dc.rights.uri info:eu-repo/semantics/openAccess
dc.source Ballester Bolinches, Adolfo Cosme i Llópez, Enric Esteban Romero, Ramón 2014 A description based on languages of the final non-deterministic automaton Theoretical Computer Science 536 1 20
dc.subject Àlgebra
dc.subject Llenguatges de programació
dc.subject Automatització
dc.title A description based on languages of the final non-deterministic automaton
dc.type info:eu-repo/semantics/article
dc.date.updated 2015-11-12T11:41:20Z
dc.identifier.doi http://dx.doi.org/10.1016/j.tcs.2014.01.018
dc.identifier.idgrec 098276

View       (531.0Kb)

This item appears in the following Collection(s)

Show simple item record

Search DSpace

Advanced Search

Browse

Statistics