LTL$_f$ Learning Meets Boolean Set Cover
By: Gabriel Bathie , Nathanaël Fijalkow , Théo Matricon and more
Potential Business Impact:
Finds computer rules much faster.
Learning formulas in Linear Temporal Logic (LTLf) from finite traces is a fundamental research problem which has found applications in artificial intelligence, software engineering, programming languages, formal methods, control of cyber-physical systems, and robotics. We implement a new CPU tool called Bolt improving over the state of the art by learning formulas more than 100x faster over 70% of the benchmarks, with smaller or equal formulas in 98% of the cases. Our key insight is to leverage a problem called Boolean Set Cover as a subroutine to combine existing formulas using Boolean connectives. Thanks to the Boolean Set Cover component, our approach offers a novel trade-off between efficiency and formula size.
Similar Papers
Zero-Shot Instruction Following in RL via Structured LTL Representations
Artificial Intelligence
Teaches robots to follow complex, multi-step instructions.
Learning Probabilistic Temporal Logic Specifications for Stochastic Systems
Logic in Computer Science
Teaches computers to understand random actions.
A Compositional Framework for On-the-Fly LTLf Synthesis
Artificial Intelligence
Helps computers make better decisions from rules.