Weak $ω$-Regular Trace Languages

Mazurkiewicz traces describe concurrent behaviors of distributed systems. Trace-closed word languages, which are "linearizations" of trace languages, constitute a weaker notion of concurrency but still give us tools to investigate the latter. In this vein, our contribution is twofold. Firstly, we develop definitions that allow classification of $ω$-regular trace languages in terms of the corresponding trace-closed $ω$-regular word languages, capturing E-recognizable (reachability) and (deterministically) Büchi recognizable languages. Secondly, we demonstrate the first automata-theoretic result that shows the equivalence of $ω$-regular trace-closed word languages and Boolean combinations of deterministically $I$-diamond Büchi recognizable trace-closed languages.

No reviews yet.

No comments yet.