License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2020.19
URN: urn:nbn:de:0030-drops-128319
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12831/
Go to the corresponding LIPIcs Volume Portal

Adsul, Bharat ; Gastin, Paul ; Sarkar, Saptarshi ; Weil, Pascal

Wreath/Cascade Products and Related Decomposition Results for the Concurrent Setting of Mazurkiewicz Traces

pdf-format:
LIPIcs-CONCUR-2020-19.pdf (0.5 MB)

Abstract

We develop a new algebraic framework to reason about languages of Mazurkiewicz traces. This framework supports true concurrency and provides a non-trivial generalization of the wreath product operation to the trace setting. A novel local wreath product principle has been established. The new framework is crucially used to propose a decomposition result for recognizable trace languages, which is an analogue of the Krohn-Rhodes theorem. We prove this decomposition result in the special case of acyclic architectures and apply it to extend Kamp’s theorem to this setting. We also introduce and analyze distributed automata-theoretic operations called local and global cascade products. Finally, we show that aperiodic trace languages can be characterized using global cascade products of localized and distributed two-state reset automata.

BibTeX - Entry

@InProceedings{adsul_et_al:LIPIcs:2020:12831,
  author =	{Bharat Adsul and Paul Gastin and Saptarshi Sarkar and Pascal Weil},
  title =	{{Wreath/Cascade Products and Related Decomposition Results for the Concurrent Setting of Mazurkiewicz Traces}},
  booktitle =	{31st International Conference on Concurrency Theory (CONCUR 2020)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-160-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{171},
  editor =	{Igor Konnov and Laura Kov{\'a}cs},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12831},
  URN =		{urn:nbn:de:0030-drops-128319},
  doi =		{10.4230/LIPIcs.CONCUR.2020.19},
  annote =	{Keywords: Mazurkiewicz traces, asynchronous automata, wreath product, cascade product, Krohn Rhodes decomposition theorem, local temporal logic over traces}
}

Keywords: Mazurkiewicz traces, asynchronous automata, wreath product, cascade product, Krohn Rhodes decomposition theorem, local temporal logic over traces
Collection: 31st International Conference on Concurrency Theory (CONCUR 2020)
Issue Date: 2020
Date of publication: 26.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI