DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2026.26

Minimal and Canonical Quotients for Simulation Equivalences

Authors: Eduardo Costa Martins and Tim A. C. Willemse

Published in: LIPIcs, Volume 391, 37th International Conference on Concurrency Theory (CONCUR 2026)

Abstract

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.

Cite as

Eduardo Costa Martins and Tim A. C. Willemse. Minimal and Canonical Quotients for Simulation Equivalences. In 37th International Conference on Concurrency Theory (CONCUR 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 391, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{costamartins_et_al:LIPIcs.CONCUR.2026.26,
  author =	{Costa Martins, Eduardo and Willemse, Tim A. C.},
  title =	{{Minimal and Canonical Quotients for Simulation Equivalences}},
  booktitle =	{37th International Conference on Concurrency Theory (CONCUR 2026)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-447-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{391},
  editor =	{Sokolova, Ana and Totzke, Patrick},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2026.26},
  URN =		{urn:nbn:de:0030-drops-273725},
  doi =		{10.4230/LIPIcs.CONCUR.2026.26},
  annote =	{Keywords: Coupled Similarity, Weak Simulation, Minimisation}
}

Search Results

Documents authored by Costa Martins, Eduardo

Minimal and Canonical Quotients for Simulation Equivalences

Abstract

Cite as

Thanks for your feedback!

Could not send message