Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Gérard Cece Connect in order to contact the contributor
Submitted on : Thursday, February 14, 2013 - 1:31:04 PM
Last modification on : Thursday, January 13, 2022 - 12:00:18 PM
Long-term archiving on: : Wednesday, May 15, 2013 - 3:58:19 AM


Files produced by the author(s)


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


Gérard Cece. Bisimulations over DLTS in O(m.log n)-time. {date}. ⟨hal-00788402⟩



Record views


Files downloads