cs.LGDec 26, 2023

Learning temporal formulas from examples is hard

Authors: Corto Mascle, Nathanaël Fijalkow, Guillaume Lagarde

Organizations: LaBRI, University of Bordeaux, France · CNRS, LaBRI, Université de Bordeaux, France

Abstract

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. Given positive and negative words, the goal is to find a smallest formula satisfied by the positive words and not by the negative ones. We study the computational complexity of this problem for all fragments of negation-free LTL built from the operators F (eventually), G (globally), X (next), ∧\wedge (conjunction), and ∨\vee (disjunction), without the until operator. We show that the problem is in NP for all fragments, that it is in polynomial time for the fragments containing none of the pairs {X,∧}\{X,\wedge\}, {X,∨}\{X,\vee\}, {F,∧}\{F,\wedge\} and {G,∨}\{G,\vee\}, and that it is NP-complete for all other fragments, already for alphabets with two or three letters. We also show that the fragment with only X and ∧\wedge has a polynomial time 3-approximation algorithm, but no polynomial time approximation scheme unless P = NP. These results motivate the search for efficient heuristics.

Figures & tables

Explore similar work

CardsList
  1. Infinite Trace Objectives with Finite Trace Techniques: Translating LTL to LTLf+

    Aug 3, 2026Christoph Weinhuber, Maximilian Prokop, Giuseppe De Giacomo +1Temporal ReasoningFormal Verification

  2. Syntax Is Easy, Semantics Is Hard: Evaluating LLMs for LTL Translation

    Apr 8, 2026Priscilla Kyei Danso, Mohammad Saqib Hasan, Niranjan Balasubramanian +1Linear Temporal LogicLLM Evaluation