The Complexity of Learning Linear Temporal Formulas from Examples
  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.
