2026-08-25T22:09:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27372 2026-08-24T14:08:31Z ddc:004 open_access

Minimal and Canonical Quotients for Simulation Equivalences Costa Martins, Eduardo Willemse, Tim A. C. Coupled Similarity Weak Simulation Minimisation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eduardo Costa Martins and Tim A. C. Willemse 2026 Is Part Of LIPIcs, Volume 391, 37th International Conference on Concurrency Theory (CONCUR 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2026.26 urn:nbn:de:0030-drops-273725 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2026.26 eng https://creativecommons.org/licenses/by/4.0/legalcode