Threshold-Based Behavioural Distances
Forster J, Schröder L, Wild P, König B, Nora P (2026)
Publication Type: Conference contribution
Publication year: 2026
Journal
Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Book Volume: 391
Conference Proceedings Title: Leibniz International Proceedings in Informatics, LIPIcs
Event location: Liverpool, GBR
ISBN: 9783959774475
DOI: 10.4230/LIPIcs.CONCUR.2026.35
Abstract
Behavioural distances generally offer more fine-grained means of comparing quantitative systems than two-valued behavioural equivalences. They often relate to quantitative modal logics that characterize a given behavioural distance in terms of the induced logical distance. We develop a unified framework for behavioural distances and logics induced by a special type of modalities that lift two-valued predicates to quantitative predicates. A typical example is the probability operator, which maps a two-valued predicate A to a quantitative predicate on probability distributions assigning to each distribution the respective probability of A. Correspondingly, the prototypical example of our framework is ε-bisimulation distance of Markov chains, which has recently been shown to coincide with the behavioural distance induced by the popular Lévy-Prokhorov distance on distributions. Other examples include behavioural distance on metric transition systems and Hausdorff behavioural distance on fuzzy transition systems. We establish a number of general results in this framework, including existence and polynomial-time computation of distinguishing formulae in two characteristic modal logics: A two-valued logic with a notion of satisfaction up to ε, and a quantitative logic. These general results instantiate to new results in many of the mentioned examples. Notably, we obtain polynomial-time computation of distinguishing formulae for ε-bisimulation distance of Markov chains in a quantitative logic featuring a “generally” modality used in probabilistic knowledge representation.
Authors with CRIS profile
Jonas Forster
Lehrstuhl für Informatik 8 (Theoretische Informatik)
Lutz Schröder
Lehrstuhl für Informatik 8 (Theoretische Informatik)
Paul Wild
Lehrstuhl für Informatik 8 (Theoretische Informatik)
Involved external institutions
Germany (DE)How to cite
APA:
Forster, J., Schröder, L., Wild, P., König, B., & Nora, P. (2026). Threshold-Based Behavioural Distances. In Ana Sokolova, Patrick Totzke (Eds.), Leibniz International Proceedings in Informatics, LIPIcs. Liverpool, GBR: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.
MLA:
Forster, Jonas, et al. "Threshold-Based Behavioural Distances." Proceedings of the 37th International Conference on Concurrency Theory, CONCUR 2026, Liverpool, GBR Ed. Ana Sokolova, Patrick Totzke, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2026.
BibTeX: Download