Learning temporal formulas from examples is hard

Corto Mascle, Nathanaël Fijalkow, Guillaume Lagarde
12/26/2023
cs.LGcs.AIcs.FL

No confident code implementation found for this paper.

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. 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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Cite this paper

@article{mascle2023learning,
  title  = {Learning temporal formulas from examples is hard},
  author = {Corto Mascle and Nathanaël Fijalkow and Guillaume Lagarde},
  year   = {2023},
  eprint = {2312.16336},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2312.16336v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2312.16336.svg)](https://codeofpaper.com/paper/2312.16336)

Discussion