Bharat Adsul ; Paul Gastin ; Saptarshi Sarkar ; Pascal Weil - Asynchronous wreath product and cascade decompositions for concurrent behaviours

lmcs:7504 - Logical Methods in Computer Science, June 28, 2022, Volume 18, Issue 2 -
Asynchronous wreath product and cascade decompositions for concurrent behaviours

Authors: Bharat Adsul ; Paul Gastin ; Saptarshi Sarkar ; Pascal Weil

We develop new algebraic tools to reason about concurrent behaviours modelled as languages of Mazurkiewicz traces and asynchronous automata. These tools reflect the distributed nature of traces and the underlying causality and concurrency between events, and can be said to support true concurrency. They generalize the tools that have been so efficient in understanding, classifying and reasoning about word languages. In particular, we introduce an asynchronous version of the wreath product operation and we describe the trace languages recognized by such products (the so-called asynchronous wreath product principle). We then propose a decomposition result for recognizable trace languages, analogous to the Krohn-Rhodes theorem, and we prove this decomposition result in the special case of acyclic architectures. Finally, we introduce and analyze two distributed automata-theoretic operations. One, the local cascade product, is a direct implementation of the asynchronous wreath product operation. The other, global cascade sequences, although conceptually and operationally similar to the local cascade product, translates to a more complex asynchronous implementation which uses the gossip automaton of Mukund and Sohoni. This leads to interesting applications to the characterization of trace languages definable in first-order logic: they are accepted by a restricted local cascade product of the gossip automaton and 2-state asynchronous reset automata, and also by a global cascade sequence of 2-state asynchronous reset automata. Over distributed alphabets for which the asynchronous Krohn-Rhodes theorem holds, a local cascade product of such automata is sufficient and this, in turn, leads to the identification of a simple temporal logic which is expressively complete for such alphabets.

Volume: Volume 18, Issue 2
Published on: June 28, 2022
Accepted on: June 28, 2022
Submitted on: May 25, 2021
Keywords: Computer Science - Formal Languages and Automata Theory


Consultation statistics

This page has been seen 229 times.
This article's PDF has been downloaded 232 times.