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
| CREATOR | Jonas Forster, Lutz Schröder, Paul Wild, Barbara König, Pedro Nora |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 110 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-12084