CONCUR

Minimal and Canonical Quotients for Simulation Equivalences

Eduardo Costa Martins, Tim Willemse

in Room Ain session CONCUR Session 4 - (Bi)Simulations (on, Tue, 16:30, 3 talks over 70 min)

Quotients have only been studied for a handful of equivalences in the linear time-branching time spectrum, for which there are results pertaining to canonicity and minimality. We extend these results to weak simulation equivalence and coupled similarity, two closely related equivalences induced by simulation preorders. We describe abstract procedures for transforming an LTS into a unique representative of its equivalence class, and for transforming an LTS into an equivalent state- and transition-minimal LTS. Moreover, we show the minimisation problem is NP-complete.

Other talks in CONCUR Session 4 - (Bi)Simulations:

Revisiting True Concurrency Bisimilarities: On the Role of Backward Ready Multisets and Why They Are Not Enough for HPB and HHPB
Wheeler Bisimulations

Program CONCUR Program