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

Abstract : 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.
Type de document :
Pré-publication, Document de travail
Submitted to DLT'13. 2013
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00788402
Contributeur : Gérard Cece <>
Soumis le : jeudi 14 février 2013 - 13:31:04
Dernière modification le : jeudi 15 février 2018 - 08:48:07
Document(s) archivé(s) le : mercredi 15 mai 2013 - 03:58:19

Fichiers

bisimDLTS_hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00788402, version 1
  • ARXIV : 1302.3489

Citation

Gérard Cece. Bisimulations over DLTS in O(m.log n)-time. Submitted to DLT'13. 2013. 〈hal-00788402〉

Partager

Métriques

Consultations de la notice

122

Téléchargements de fichiers

60