Learning temporal formulas from examples is hard
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), (conjunction), and (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 , , and , 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 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
| Operators | Fixed alphabet | Alphabet part of the input |
| , , or | in , and a minimal formula can be computed (Thm. 6 ) | same |
| in (Thm. 6 ) | -complete (Thms. 2 and 5 ) | |
| or | -complete for (Thms. 10 and 5 ) | same |
| -complete for (Thms. 11 and 5 ) | -complete | |
| -complete for (Thms. 12 and 5 ) | -complete | |
| Approximation. has a polynomial-time -approximation algorithm (Thm. 7 ) and is -hard (Thm. 9 ). is -hard (Thm. 9 ) and has a -approximation algorithm. When the alphabet is part of the input, cannot be approximated within unless (Thm. 4 ). | ||