Constructive Preference Relations: Navigating Undecidability in Rational LTL Contraction
Source: arXiv:2606.16957 · Published 2026-06-15 · By Hannes Gaißer, Dominik Klumpp, Jandson S. Ribeiro
TL;DR
This paper investigates the computational challenges of belief contraction in linear temporal logic (LTL), focusing on the construction and verification of epistemic preference relations that underpin rational contraction operations. While rational belief contraction—removing obsolete beliefs with minimal change—is well-studied in classical logics, extending this to expressive temporal logics like LTL presents new difficulties due to infinite time structures and automata-based representation. The authors analyze the key properties required for such preference relations, namely Mirroring and Maximal Cut, proving that Mirroring is decidable but Maximal Cut is undecidable when preferences are represented via Büchi-Mealy automata (BMA). To circumvent this fundamental undecidability, they propose constructive families of preference relations that satisfy these properties by design. These constructions generalize classical distance measures (e.g., Dalal) and enable hierarchical composition of preference relations, thus providing a practical pathway to fully rational LTL belief contraction despite theoretical limitations. The work significantly advances understanding of the interplay between temporal logic, automata theory, and rational belief change from a computational perspective.
Key findings
- Mirroring condition for preference relations encoded as Büchi-Mealy automata is decidable in exponential time (Theorem 17).
- Maximal Cut condition, which guarantees contraction success, is undecidable for Büchi-Mealy automata preference relations (Theorem 27).
- Maximal Cut and well-foundedness properties coincide on preference relations induced by Büchi automata encoding Linear Bounded Automata, enabling the undecidability reduction.
- There exist Büchi-Mealy automata relations satisfying Mirroring and Maximal Cut without being well-founded (Proposition 20), showing expressive limits of these properties in LTL.
- Constructive families of preference relations are provided that ensure Mirroring and Maximal Cut by design, allowing effective computation of fully rational LTL contractions (Section 5).
- The negative undecidability results imply no complete semi-decision procedure or representation theorem for Maximal Cut on Büchi-Mealy automata exists (Observation 28).
- Use of Büchi-Mealy automata to represent epistemic preference relations enables computable Büchi choice functions for contraction but requires careful syntactic constraints.
Threat model
The adversary is an automated verifier or construction system attempting to determine whether a given Büchi-Mealy automaton encoding an epistemic preference relation satisfies the core conditions (Mirroring and Maximal Cut) necessary for rational belief contraction in LTL. The adversary has full access to the automaton and machinery to perform automata operations and decision procedures but cannot circumvent fundamental theoretical undecidability results.
Methodology — deep read
The authors examine the computational viability of preference relations used in rational belief contraction operators in LTL. They set the threat model as formal verification of whether an encoded preference relation satisfies rationality properties essential for contraction (Mirroring and Maximal Cut).
Data consists of automata representations: Büchi automata denote LTL formula satisfaction sets, and Büchi-Mealy automata (BMA) represent binary preference relations over infinite traces of atomic propositions.
The analysis begins with formal definitions of LTL formulae, semantics, Büchi automata, and Büchi-Mealy automata. They leverage established automata-theoretic operations (union, intersection, complement, relational composition, inverse) and known decidability results for Büchi automata inclusion to frame the decision problems.
The key properties are recast algebraically: Mirroring corresponds to an inclusion property on relational compositions of BMA relations (Lemma 15). By constructing the BMA that encodes these algebraic expressions, Mirroring can be decided via automata inclusion in exponential time (Theorem 17).
For Maximal Cut, equivalent to the existence of maximal elements in the preference ordering over any LTL-definable set of traces, the authors reduce undecidability from the LBA immortality problem—a known undecidable problem about infinite runs on linear bounded automata. They construct a Büchi-Mealy automaton simulating LBA configuration transitions and show that Maximal Cut coincides with well-foundedness of the induced relation on this class.
This reduction is achieved by representing successive LBA configurations as trace pairs accepted by a BMA and linking infinite ascending preference chains to immortal configurations.
The training regime analog does not apply—this is a theoretical computability and automata construction proof-based work. The evaluation protocol is formal decidability and complexity proofs, reductions, and construction of counterexamples or explicit examples.
For reproducibility, the paper provides detailed constructions and theoretical proofs amenable to mechanization given domain expertise and standard automata libraries. No code or datasets are explicitly released, as this is formal logic and automata theory research.
A concrete example involves the Büchi-Mealy automaton encoding preferences over rain propositions in Figure 2, illustrating how preferences between infinite traces correspond to runs accepting specific input pairs and how the properties hold.
Overall, the methodology is a rigorous theoretical computer science treatment of formal properties of infinite automata-based preference relations, demonstrating decidability boundaries and proposing constructive approximations to navigate undecidability.
Technical innovations
- Proving Mirroring condition decidable for Büchi-Mealy automata-based preference relations via algebraic relational operators and automata inclusion.
- Reducing undecidability of Maximal Cut condition to the LBA immortality problem by constructing Büchi-Mealy automata that simulate LBA runs.
- Demonstrating the disconnect between Maximal Cut and well-foundedness in LTL with finitely representable relations, highlighting expressivity gaps.
- Providing novel constructive families of preference relations that guarantee Mirroring and Maximal Cut by design, enabling effective and fully rational LTL contraction.
- Extending classical preference distance measures such as Dalal beyond propositional logic to temporal logics with automata representation.
Baselines vs proposed
- Mirroring condition decision problem for BMA: baseline undecidability unknown, proven decidable in ExpTime (Theorem 17).
- Maximal Cut condition decision problem for BMA: undecidable (Theorem 27).
- Well-foundedness decision problem for BMA: undecidable (Theorem 25).
Limitations
- Maximal Cut property is undecidable for Büchi-Mealy automata preference relations, limiting general automated verification.
- No complete constructive or syntactic characterization of all fully rational preference relations is possible due to undecidability.
- The constructions ensuring rationality by design are necessarily incomplete—they do not represent all possible preference relations meeting Maximal Cut.
- Results rest on infinite automata-theoretic representations; hence practical implementations must manage complexity and potentially infinite-state reasoning.
- No empirical evaluation or tool implementation is provided; practicality remains theoretical and subject to follow-up engineering.
- The undecidability results hold even when restricting to simple temporal operators (e.g., next), showing inherent complexity.
Open questions / follow-ons
- Can broader classes of practically useful preference relations in LTL be characterized that avoid undecidability while maintaining expressiveness?
- What is the complexity and efficacy of the proposed constructive preference relation families when instantiated for real-world belief change scenarios?
- How do preference relation constructions generalize to other temporal or modal logics beyond LTL?
- Can approximations or heuristics be formally analyzed to provide semi-decision procedures or partial verification for Maximal Cut in practice?
Why it matters for bot defense
From a bot-defense or CAPTCHA perspective, this work deals with the logical foundations of rational belief update under temporal reasoning, a domain generally tangential to direct bot detection mechanisms. However, the paper’s formal treatment of preference relations and contraction operators could inspire methodologies for managing evolving threat models or agent knowledge over time. For example, adaptive CAPTCHA difficulty or challenge selection mechanisms might benefit from logically principled minimal-change updates to attacker models encoded with temporal behavior patterns.
The undecidability results underscore fundamental limits in fully automated reasoning about complex infinite temporal preferences, which cautions against expecting fully general algorithmic guarantees for dynamic belief updates in security contexts involving temporal or sequential patterns. The constructive families provide a pathway to effective yet incomplete approximate solutions, a trade-off relevant for implementing practical, scalable bot defenses that incorporate temporal logic constraints.
Cite
@article{arxiv2606_16957,
title={ Constructive Preference Relations: Navigating Undecidability in Rational LTL Contraction },
author={ Hannes Gaißer and Dominik Klumpp and Jandson S. Ribeiro },
journal={arXiv preprint arXiv:2606.16957},
year={ 2026 },
url={https://arxiv.org/abs/2606.16957}
}