mlsanityData to 14 Oct 2026

The Complexity of Learning Linear Temporal Formulas from Examples

arXiv 2102.00876 ↗First posted 1 Feb 2021cs.FL cs.LG cs.LOcited by 12

Not on the map. Why?

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.

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

2 of 24 references.

References · 2

  1. 2018Learning Linear Temporal Propertiescited by 41
  2. 2020Learning Interpretable Models in the Property Specification Languagecited by 11

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 1; 2023: 4; 2024: 3; 2025: 3.

12 papers.

  1. 2021Scalable Anytime Algorithms for Learning Fragments of Linear Temporal Logiccited by 9
  2. 2024LTL learning on GPUscited by 6
  3. 2023Learning temporal formulas from examples is hardcited by 4
  4. 2023Synthesizing Efficiently Monitorable Formulas in Metric Temporal Logiccited by 3
  5. 2023Reverse Engineering of Temporal Queries Mediated by LTL Ontologiescited by 1
  6. 2024Learning to Estimate System Specifications in Linear Temporal Logic using Transformers and Mambacited by 1
  7. 2025LTLf Learning Meets Boolean Set Covercited by 1
  8. 2022Specification sketching for Linear Temporal Logiccited by 0
  9. 2023Unique Characterisability and Learnability of Temporal Queries Mediated by an Ontologycited by 0
  10. 2024Learning Interpretable Classifiers for PDDL Planningcited by 0
  11. 2025Automata Learning of Preferences over Temporal Logic Formulas from Pairwise Comparisonscited by 0
  12. 2025Interpretable Early Failure Detection via Machine Learning and Trace Checking-based Monitoringcited by 0