Bisimulations over DLTS in O(m.log n)-time - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2013

Bisimulations over DLTS in O(m.log n)-time

Résumé

The well known Hopcroft's algorithm to minimize deterministic complete automata runs in $O(kn\log n)$-time, where $k$ is the size of the alphabet and $n$ the number of states. The main part of this algorithm corresponds to the computation of a coarsest bisimulation over a finite Deterministic Labelled Transition System (DLTS). By applying techniques we have developed in the case of simulations, we design a new algorithm which computes the coarsest bisimulation over a finite DLTS in $O(m\log n)$-time and $O(k+m+n)$-space, with $m$ the number of transitions. The underlying DLTS does not need to be complete and thus: $m\leq kn$. This new algorithm is much simpler than the two others found in the literature.
Fichier principal
Vignette du fichier
bisimDLTS_hal.pdf (167.16 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00788402 , version 1 (14-02-2013)

Identifiants

Citer

Gérard Cece. Bisimulations over DLTS in O(m.log n)-time. 2013. ⟨hal-00788402⟩
93 Consultations
50 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More