Constructive Preference Relations: Navigating Undecidability in Rational LTL Contraction
2026-06-15 • Logic in Computer Science
Logic in Computer Science
AI summaryⓘ
The authors look at how to manage changing beliefs over time using a logic called linear temporal logic (LTL). They focus on preference relations, which help decide which beliefs to drop when they become outdated. While creating these relations is usually simple, the authors show it's actually very hard and sometimes impossible (undecidable) when using LTL. To fix this, they design new ways to build these relations that are guaranteed to work, including generalizing known distance measures and combining different preferences step-by-step. Their work expands what is possible for belief change both in LTL and traditional logical systems.
linear temporal logicepistemic preferencesbelief contractionBüchi automataundecidabilitypreference relationsDalal distancerational belief changehierarchical composition
Authors
Hannes Gaißer, Dominik Klumpp, Jandson S. Ribeiro
Abstract
We study the computational aspects of epistemic preference relations in non-classical logics, particularly linear temporal logic (LTL). Epistemic preferences form the backbone of belief contraction operators, which describe how to rationally relinquish obsolete beliefs. These preference relations have to satisfy certain innocuous conditions; and constructing such relations is usually assumed to be a trivial process. However, in the case of LTL, where relations are represented with Büchi automata, we show that this is a challenging task: the core condition, which guarantees the success of contraction, is in fact undecidable. Towards achieving effective LTL belief contraction, we then propose several concrete constructions of novel preference relations that satisfy the required conditions by design. These constructions include, among others, (1) generalisations of distance measures (e.g. Dalal) beyond the classical setting, as well as (2) the ability to hierarchically compose different preference relations. Our results not only provide rich families of preference relations for LTL, but also generalise the limited pool of concrete preference relations for the classical cases, allowing us to go beyond Dalal to achieve full rationality.