Identity-Preserving Lax Extensions and Where to Find Them

Goncharov S, Hofmann D, Nora P, Schröder L, Wild P (2025)


Publication Type: Conference contribution

Publication year: 2025

Journal

Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Book Volume: 327

Conference Proceedings Title: Leibniz International Proceedings in Informatics, LIPIcs

Event location: Jena DE

ISBN: 9783959773652

DOI: 10.4230/LIPIcs.STACS.2025.40

Abstract

Generic notions of bisimulation for various types of systems (nondeterministic, probabilistic, weighted etc.) rely on identity-preserving (normal) lax extensions of the functor encapsulating the system type, in the paradigm of universal coalgebra. It is known that preservation of weak pullbacks is a sufficient condition for a functor to admit a normal lax extension (the Barr extension, which in fact is then even strict); in the converse direction, nothing is currently known about necessary (weak) pullback preservation conditions for the existence of normal lax extensions. In the present work, we narrow this gap by showing on the one hand that functors admitting a normal lax extension preserve 1/4-iso pullbacks, i.e. pullbacks in which at least one of the projections is an isomorphism. On the other hand, we give sufficient conditions, showing that a functor admits a normal lax extension if it weakly preserves either 1/4-iso pullbacks and 4/4-epi pullbacks (i.e. pullbacks in which all morphisms are epic) or inverse images. We apply these criteria to concrete examples, in particular to functors modelling neighbourhood systems and weighted systems.

Authors with CRIS profile

Involved external institutions

How to cite

APA:

Goncharov, S., Hofmann, D., Nora, P., Schröder, L., & Wild, P. (2025). Identity-Preserving Lax Extensions and Where to Find Them. In Olaf Beyersdorff, Michal Pilipczuk, Elaine Pimentel, Nguyen Kim Thang (Eds.), Leibniz International Proceedings in Informatics, LIPIcs. Jena, DE: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.

MLA:

Goncharov, Sergey, et al. "Identity-Preserving Lax Extensions and Where to Find Them." Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025, Jena Ed. Olaf Beyersdorff, Michal Pilipczuk, Elaine Pimentel, Nguyen Kim Thang, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2025.

BibTeX: Download