Skip to Main content Skip to Navigation
Book sections

Scalable Anytime Algorithms for Learning Fragments of Linear Temporal Logic

Abstract : Abstract Linear temporal logic (LTL) is a specification language for finite sequences (called traces) widely used in program verification, motion planning in robotics, process mining, and many other areas. We consider the problem of learning formulas in fragments of LTL without the $$\mathbf {U}$$ U -operator for classifying traces; despite a growing interest of the research community, existing solutions suffer from two limitations: they do not scale beyond small formulas, and they may exhaust computational resources without returning any result. We introduce a new algorithm addressing both issues: our algorithm is able to construct formulas an order of magnitude larger than previous methods, and it is anytime, meaning that it in most cases successfully outputs a formula, albeit possibly not of minimal size. We evaluate the performances of our algorithm using an open source implementation against publicly available benchmarks.
Document type :
Book sections
Complete list of metadata

https://hal-cnrs.archives-ouvertes.fr/hal-03775030
Contributor : Nathanaël Fijalkow Connect in order to contact the contributor
Submitted on : Monday, September 12, 2022 - 11:49:57 AM
Last modification on : Monday, September 12, 2022 - 11:49:58 AM

Links full text

Identifiers

Collections

Citation

Ritam Raha, Rajarshi Roy, Nathanaël Fijalkow, Daniel Neider. Scalable Anytime Algorithms for Learning Fragments of Linear Temporal Logic. Tools and Algorithms for the Construction and Analysis of Systems, 13243, Springer International Publishing, pp.263-280, 2022, Lecture Notes in Computer Science, ⟨10.1007/978-3-030-99524-9_14⟩. ⟨hal-03775030⟩

Share

Metrics

Record views

0