Nathanaël Fijalkow and Guillaume Lagarde
Link to the paper: here
Abstract: 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 the fragment containing only the next operator and conjunctions, and prove NP-hardness results for many fragments
Any question or comment can be made using the comment section of the page below.