Bisimilarity Minimization in O(m logn) Time

DOI10.1007/978-3-642-02424-5_9zbMath1242.68186OpenAlexW1563368561MaRDI QIDQ3636842

Antti Valmari

Publication date: 30 June 2009

Published in: Applications and Theory of Petri Nets (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02424-5_9

zbMATH Keywords

analysis of reachability graphsverification of systems

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items

An O ( m log n ) Algorithm for Computing Stuttering Equivalence and Branching Bisimulation, Minimality Notions via Factorization Systems and Examples, Unnamed Item, Fast brief practical DFA minimization, From generic partition refinement to weighted tree automata minimization, Persistent Stochastic Non-Interference, An O(m log n) algorithm for branching bisimilarity on labelled transition systems, Causal Semantics for BPP Nets with Silent Moves, Efficient Coalgebraic Partition Refinement

Cites Work

• An implementation of an efficient algorithm for bisimulation equivalence
• Characterizing finite Kripke structures in propositional temporal logic
• Re-describing an algorithm by Hopcroft
• An efficient algorithm for computing bisimulation equivalence
• Describing an algorithm by Hopcroft
• Three Partition Refinement Algorithms
• Efficient Minimization of DFAs with Partial Transition Functions
• Unnamed Item
• Unnamed Item
• Unnamed Item