Mission-time LTL (MLTL) Formula Validation Via Regular Expressions

Zili Wang, Chiara Travesset, Jeremy Sorkin, Jenna Elwing, Laura P.Gamboa-Guzman and Kristin Yvonne Rozier

This webpage contains supplementary material for "Mission-time LTL (MLTL) Formula Validation Via Regular Expressions" by J. Elwing L. Gamboa-Guzman, K.Y. Rozier, J. Sorkin, C. Travesset, and Z. Wang

Abstract

Mission-time Linear Temporal Logic (MLTL) represents the most practical fragment of Metric Temporal Logic; MLTL resembles the popular logic Linear Temporal Logic (LTL) with finite closed-interval integer bounds on the temporal operators. Increasingly, many tools reason over MLTL specifications, yet these tools are useful only when system designers can validate the input specifications. We design an automated characterization of the structure of the computations that satisfy a given MLTL formula using regular expressions. We prove the soundness and completeness of our structure. We also give an algorithm for automated MLTL formula validation and analyze its complexity both theoretically and experimentally. Additionally, we generate a test suite using control flow diagrams to robustly test our implementation and release an open-source tool with a user-friendly graphical interface. The result of our contributions are improvements to existing algorithms for MLTL analysis and are applicable to many other tools for automated, efficient MLTL formula validation.