تقرير
Learning temporal formulas from examples is hard
| العنوان: | Learning temporal formulas from examples is hard |
|---|---|
| المؤلفون: | Mascle, Corto, Fijalkow, Nathanaël, Lagarde, Guillaume |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Machine Learning, Computer Science - Artificial Intelligence, Computer Science - Formal Languages and Automata Theory, Computer Science - Logic in Computer Science |
| الوصف: | 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 this paper we initiate the study of the computational complexity of the problem. Our main results are hardness results: we show that the LTL learning problem is NP-complete, both for the full logic and for almost all of its fragments. This motivates the search for efficient heuristics, and highlights the complexity of expressing separating properties in concise natural language. Comment: This article is a long version of the article arXiv:2102.00876 presented in the International Conference on Grammatical Inference (ICGI) in 2021. It includes much stronger and more general results than the extended abstract. Submitted to a journal |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2312.16336 |
| رقم الأكسشن: | edsarx.2312.16336 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |