The complexity of learning linear temporal formulas from examples

Nathanaël Fijalkow, Guillaume Lagarde
Proceedings of the Fifteenth International Conference on Grammatical Inference, PMLR 153:237-250, 2021.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v153-fijalkow21a, title = {The complexity of learning linear temporal formulas from examples}, author = {Fijalkow, Nathana\"el and Lagarde, Guillaume}, booktitle = {Proceedings of the Fifteenth International Conference on Grammatical Inference}, pages = {237--250}, year = {2021}, editor = {Chandlee, Jane and Eyraud, Rémi and Heinz, Jeff and Jardine, Adam and van Zaanen, Menno}, volume = {153}, series = {Proceedings of Machine Learning Research}, month = {23--27 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v153/fijalkow21a/fijalkow21a.pdf}, url = {https://proceedings.mlr.press/v153/fijalkow21a.html}, 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. } }
Endnote
%0 Conference Paper %T The complexity of learning linear temporal formulas from examples %A Nathanaël Fijalkow %A Guillaume Lagarde %B Proceedings of the Fifteenth International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2021 %E Jane Chandlee %E Rémi Eyraud %E Jeff Heinz %E Adam Jardine %E Menno van Zaanen %F pmlr-v153-fijalkow21a %I PMLR %P 237--250 %U https://proceedings.mlr.press/v153/fijalkow21a.html %V 153 %X 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.
APA
Fijalkow, N. & Lagarde, G.. (2021). The complexity of learning linear temporal formulas from examples. Proceedings of the Fifteenth International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 153:237-250 Available from https://proceedings.mlr.press/v153/fijalkow21a.html.

Related Material