# Automata Learning of Preferences over Temporal Logic Formulas from Pairwise Comparisons

arXiv: https://arxiv.org/abs/2505.18030 · HTML: https://mlsanity.com/paper/2505.18030/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 43 references that are in the map.
- First posted on arXiv 23 May 2025.

## Builds on (most cited first, 19 of 19)

- [A Survey of Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2312.14925/) (2023)
- [Learning Linear Temporal Properties](https://mlsanity.com/paper/1806.03953/) (2018)
- [Specifying User Preferences using Weighted Signal Temporal Logic](https://mlsanity.com/paper/2010.00752/) (2020)
- [Active Preference Learning using Maximum Regret](https://mlsanity.com/paper/2005.04067/) (2020)
- [Interpretable Classification of Time-Series Data using Efficient Enumerative Techniques](https://mlsanity.com/paper/1907.10265/) (2019)
- [The Complexity of Learning Linear Temporal Formulas from Examples](https://mlsanity.com/paper/2102.00876/) (2021)
- [A Robust Genetic Algorithm for Learning Temporal Specifications from Data](https://mlsanity.com/paper/1711.06202/) (2017)
- [Learning Linear Temporal Properties from Noisy Data: A MaxSAT Approach](https://mlsanity.com/paper/2104.15083/) (2021)
- [Scalable Anytime Algorithms for Learning Fragments of Linear Temporal Logic](https://mlsanity.com/paper/2110.06726/) (2021)
- [What to Do When You Can't Do It All: Temporal Logic Planning with Soft Temporal Logic Constraints](https://mlsanity.com/paper/2008.01926/) (2020)
- [Minimum-Violation Planning for Autonomous Systems: Theoretical and Practical Considerations](https://mlsanity.com/paper/2009.11954/) (2020)
- [Probabilistic Planning with Preferences over Temporal Goals](https://mlsanity.com/paper/2103.14489/) (2021)
- [SAT-based Learning of Computation Tree Logic](https://mlsanity.com/paper/2402.06366/) (2024)
- [Probabilistic Planning with Partially Ordered Preferences over Temporal Goals](https://mlsanity.com/paper/2209.12267/) (2022)
- [Learning Formal Specifications from Membership and Preference Queries](https://mlsanity.com/paper/2307.10434/) (2023)
- [Synthesizing Efficiently Monitorable Formulas in Metric Temporal Logic](https://mlsanity.com/paper/2310.17410/) (2023)
- [Probabilistic Planning with Prioritized Preferences over Temporal Logic Objectives](https://mlsanity.com/paper/2304.11641/) (2023)
- [Opportunistic Qualitative Planning in Stochastic Systems with Incomplete Preferences over Reachability Objectives](https://mlsanity.com/paper/2210.01878/) (2022)
- [Inferring Properties in Computation Tree Logic](https://mlsanity.com/paper/2310.13778/) (2023)

## Abstract (arXiv)

Many preference elicitation algorithms consider preference over propositional logic formulas or items with different attributes. In sequential decision making, a user's preference can be a preorder over possible outcomes, each of which is a temporal sequence of events. This paper considers a class of preference inference problems where the user's unknown preference is represented by a preorder over regular languages (sets of temporal sequences), referred to as temporal goals. Given a finite set of pairwise comparisons between finite words, the objective is to learn both the set of temporal goals and the preorder over these goals. We first show that a preference relation over temporal goals can be modeled by a Preference Deterministic Finite Automaton (PDFA), which is a deterministic finite automaton augmented with a preorder over acceptance conditions. The problem of preference inference reduces to learning the PDFA. This problem is shown to be computationally challenging, with the problem of determining whether there exists a PDFA of size smaller than a given integer k, consistent with the sample, being NP-Complete. We formalize the properties of characteristic samples and develop an algorithm that guarantees to learn, given a characteristic sample, the minimal PDFA equivalent to the true PDFA from which the sample is drawn. We present the method through a running example and provide detailed analysis using a robotic motion planning problem.