Computing Distinguishing Formulae for Threshold-Based Behavioural Distances

Jonas Forster, Lutz Schröder, Paul Wild, Barbara König, Pedro Nora · 2026

Read Computing Distinguishing Formulae for Threshold-Based Behavioural Distances by Jonas Forster, Lutz Schröder, Paul Wild, Barbara König, Pedro Nora (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-12084.txt.

Description

Comparing two systems that behave in shades of gray, rather than simply pass or fail, calls for a distance rather than a yes-or-no verdict. Jonas Forster and four co-authors build a single framework for such distances and the logics that describe them. It centers on modalities that lift plain yes-or-no properties into graded ones.

The classic example is the probability operator, which turns a property of outcomes into a probability over distributions. Their main results give fast, polynomial-time ways to extract distinguishing formulas in two logics. One is two-valued, with satisfaction allowed up to a small slack; the other is fully graded. The results cover Markov-chain distances, metric transition systems, and fuzzy systems, including a new extraction result for epsilon-bisimulation distance.

Catalog record

CREATORJonas Forster, Lutz Schröder, Paul Wild, Barbara König, Pedro Nora
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE110 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-12084

Browse the full library · About the Tower of Babel