论文标题
Mazurkiewicz Traces（扩展版本）并发设置的花圈/级联产品和相关分解结果
Wreath/cascade products and related decomposition results for the concurrent setting of Mazurkiewicz traces (extended version)
论文作者
论文摘要
我们开发了一个新的代数框架，以推理Mazurkiewicz痕迹的语言。该框架支持真正的并发性，并将花圈产品操作的非平凡概括为跟踪设置。已经建立了一种新型的本地花圈产品原理。新框架至关重要地用于提出可识别的微量语言的分解结果，这是Krohn-rhodes定理的类似物。我们证明了这种分解导致环环体系结构的特殊情况，并将其应用于将Kamp定理扩展到此设置。我们还介绍和分析了称为本地和全球级联产品的分布式自动机理论操作。最后，我们表明，可以使用局部和分布式两态重置自动机的全局级联产品来表征Aperiodic微量语言。
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.
