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

2013/02/14 by Cece, Gérard
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.1302.3489

Abstract

The well known Hopcroft's algorithm to minimize deterministic complete automata runs in O(knlog 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(mlog 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≤ kn. This new algorithm is much simpler than the two others found in the literature.

Related

• Three Simulation Algorithms for Labelled Transition Systems
• An O(m log n) Algorithm for Stuttering Equivalence and Branching\n Bisimulation
• Concurrent bisimulation algorithm
• A linear parallel algorithm to compute bisimulation and relational coarsest partitions
• A simpler O(m log n) algorithm for branching bisimilarity on labelled transition systems