2026-07-20T05:25:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23955 2025-11-12T13:24:55Z ddc:004 open_access

Characterizations of Fragments of Temporal Logic over Mazurkiewicz Traces Adsul, Bharat Gastin, Paul Kulkarni, Shantanu Mazurkiewicz traces temporal logics asynchronous automata cascade product Green’s relations algebraic automata theory We study fragments of temporal logics over Mazurkiewicz traces which are well known and established partial-order models of concurrent behaviours. We focus on concurrent versions of "strict past" and "strict future" modalities. Over words, the corresponding fragments have been shown to coincide with natural algebraic conditions on the recognizing monoids. We provide non-trivial generalizations of these classical results to traces. We exploit the local nature of the temporal modalities and obtain modular translations of specifications into asynchronous automata. More specifically, we provide novel characterizations of these fragments via local cascade products of a very simple two-state asynchronous automaton operating on a single process. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bharat Adsul and Paul Gastin and Shantanu Kulkarni 2025 Is Part Of LIPIcs, Volume 348, 36th International Conference on Concurrency Theory (CONCUR 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2025.5 urn:nbn:de:0030-drops-239551 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2025.5 eng https://creativecommons.org/licenses/by/4.0/legalcode