Rational and Recognizable Complex Trace Languages

Mazurkiewicz defined traces as an algebraic model of finite concurrent processes. In order to model non-terminating processes a good notion of infinite traces was needed, which finally led to the notion of complex traces. For complex traces an associative concatenation and an ω-iteration are defined. This paper defines and investigates rational and recognizable complex trace languages. We prove various closure results such as the closure under boolean operations (for recognizable languages), concatenation, and left and right quotients by recognizable sets. Then we study sufficient conditions ensuring the recognizability of the finite and infinite iterations of complex trace languages. We introduce a generalization of the notion of concurrent iteration which leads to the main result of the paper: the generalization of Kleene′s and Ochmański′s theorems to complex trace languages.

Authors

• V. Diekert
• P. Gastin
• A. Petit

Keywords

No keywords are indexed for this paper.