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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Learning temporal formulas from examples is hard
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…
Learning Temporal Logic Properties: an Overview of Two Recent Methods
Learning linear temporal logic (LTL) formulas from examples labeled as positive or negative has found applications in inferring descriptions of system behavior. We summarize two methods to learn LTL formulas from example…
SpecificityVocal Bursts Valence PredictionLearning Linear Temporal Properties
We present two novel algorithms for learning formulas in Linear Temporal Logic (LTL) from examples. The first learning algorithm reduces the learning task to a series of satisfiability problems in propositional Boolean l…
Adaptive Teaching of Temporal Logic Formulas to Learners with Preferences
Machine teaching is an algorithmic framework for teaching a target hypothesis via a sequence of examples or demonstrations. We investigate machine teaching for temporal logic formulas -- a novel and expressive hypothesis…
Learning Linear Temporal Properties from Noisy Data: A MaxSAT Approach
We address the problem of inferring descriptions of system behavior using Linear Temporal Logic (LTL) from a finite set of positive and negative examples. Most of the existing approaches for solving such a task rely on p…