# Learning temporal formulas from examples is hard

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 17 references that are in the map.
- First posted on arXiv 26 Dec 2023.

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

- [Learning Linear Temporal Properties](https://mlsanity.com/paper/1806.03953/) (2018)
- [The Complexity of Learning Linear Temporal Formulas from Examples](https://mlsanity.com/paper/2102.00876/) (2021)
- [Learning Interpretable Models in the Property Specification Language](https://mlsanity.com/paper/2002.03668/) (2020)
- [Synthesizing Efficiently Monitorable Formulas in Metric Temporal Logic](https://mlsanity.com/paper/2310.17410/) (2023)

## Built on by (most cited first, 4 of 4)

- [LTL learning on GPUs](https://mlsanity.com/paper/2402.12373/) (2024)
- [SAT-Based Bounded Fitting for the Description Logic ALC](https://mlsanity.com/paper/2507.21752/) (2025)
- [LTLf Learning Meets Boolean Set Cover](https://mlsanity.com/paper/2509.24616/) (2025)
- [Learning Interpretable Classifiers for PDDL Planning](https://mlsanity.com/paper/2410.10011/) (2024)

## Abstract (arXiv)

We study the problem of learning linear temporal logic (LTL) formulas from examples, as a first step towards expressing a property separating positive and negative instances in a way that is comprehensible for humans. In this paper we initiate the study of the computational complexity of the problem. Our main results are hardness results: we show that the LTL learning problem is NP-complete, both for the full logic and for almost all of its fragments. This motivates the search for efficient heuristics, and highlights the complexity of expressing separating properties in concise natural language.