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

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

Threshold-Based Behavioural Distances Forster, Jonas Schröder, Lutz Wild, Paul König, Barbara Nora, Pedro Behavioural distance modal logic quantitative logic coalgebra Sugeno integration 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jonas Forster and Lutz Schröder and Paul Wild and Barbara König and Pedro Nora 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.35 urn:nbn:de:0030-drops-273657 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2026.35 eng https://creativecommons.org/licenses/by/4.0/legalcode