# The Complexity of Learning Linear Temporal Formulas from Examples

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 24 references that are in the map.
- First posted on arXiv 1 Feb 2021.

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

- [Learning Linear Temporal Properties](https://mlsanity.com/paper/1806.03953/) (2018)
- [Learning Interpretable Models in the Property Specification Language](https://mlsanity.com/paper/2002.03668/) (2020)

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

- [Scalable Anytime Algorithms for Learning Fragments of Linear Temporal Logic](https://mlsanity.com/paper/2110.06726/) (2021)
- [LTL learning on GPUs](https://mlsanity.com/paper/2402.12373/) (2024)
- [Learning temporal formulas from examples is hard](https://mlsanity.com/paper/2312.16336/) (2023)
- [Synthesizing Efficiently Monitorable Formulas in Metric Temporal Logic](https://mlsanity.com/paper/2310.17410/) (2023)
- [Reverse Engineering of Temporal Queries Mediated by LTL Ontologies](https://mlsanity.com/paper/2305.01248/) (2023)
- [Learning to Estimate System Specifications in Linear Temporal Logic using Transformers and Mamba](https://mlsanity.com/paper/2405.20917/) (2024)
- [LTLf Learning Meets Boolean Set Cover](https://mlsanity.com/paper/2509.24616/) (2025)
- [Specification sketching for Linear Temporal Logic](https://mlsanity.com/paper/2206.06722/) (2022)
- [Unique Characterisability and Learnability of Temporal Queries Mediated by an Ontology](https://mlsanity.com/paper/2306.07662/) (2023)
- [Learning Interpretable Classifiers for PDDL Planning](https://mlsanity.com/paper/2410.10011/) (2024)
- [Automata Learning of Preferences over Temporal Logic Formulas from Pairwise Comparisons](https://mlsanity.com/paper/2505.18030/) (2025)
- [Interpretable Early Failure Detection via Machine Learning and Trace Checking-based Monitoring](https://mlsanity.com/paper/2508.17786/) (2025)

## Abstract (arXiv)

In this paper we initiate the study of the computational complexity of learning linear temporal logic (LTL) formulas from examples. We construct approximation algorithms for fragments of LTL and prove hardness results; in particular we obtain tight bounds for approximation of the fragment containing only the next operator and conjunctions, and prove NP-completeness results for many fragments.