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 Ochmanski′s theorems to complex trace languages.