Alberto Bombardelli ; Stefano Tonetta - Asynchronous Composition of LTL Properties over Infinite and Finite Traces

lmcs:12828 - Logical Methods in Computer Science, February 16, 2026, Volume 22, Issue 1 - https://doi.org/10.46298/lmcs-22(1:11)2026
Asynchronous Composition of LTL Properties over Infinite and Finite TracesArticle

Authors: Alberto Bombardelli ; Stefano Tonetta

    The verification of asynchronous software components poses significant challenges due to the way components interleave and exchange input/output data concurrently. Compositional strategies aim to address this by separating the task of verifying individual components on local properties from the task of combining them to achieve global properties. This paper concentrates on employing symbolic model checking techniques to verify properties specified in Linear-time Temporal Logic (LTL) on asynchronous software components that interact through data ports. Unlike event-based composition, local properties can now impose constraints on input from other components, increasing the complexity of their composition. We consider both the standard semantics over infinite traces as well as the truncated semantics over finite traces to allow scheduling components only finitely many times.

    We propose a novel LTL rewriting approach, which converts a local property into a global one while considering the interleaving of infinite or finite execution traces of components. We prove the semantic equivalence of local properties and their rewritten version projected on the local symbols. The rewriting is also optimized to reduce formula size and to leave it unchanged when the temporal property is stutter invariant. These methods have been integrated into the OCRA tool, as part of the contract refinement verification suite. Finally, the different composition approaches were compared through an experimental evaluation that covers various types of specifications.


    Volume: Volume 22, Issue 1
    Published on: February 16, 2026
    Accepted on: December 5, 2025
    Submitted on: January 5, 2024
    Keywords: Logic in Computer Science

    Consultation statistics

    This page has been seen 27 times.
    This article's PDF has been downloaded 13 times.