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 comp lex traces. For complex traces an associative concatenation and an ome ga-iteration are defined. This paper defines and investigates rational and recognizable complex trace languages. We prove various closure re sults such as the closure under boolean operations (for recognizable l anguages), concatenation, and left and right quotients by recognizable sets. Then we study sufficient conditions ensuring the recognizabilit y of the finite and infinite iterations of complex trace languages. We introduce a generalization of the notion of concurrent iteration whic h leads to the main result of the paper: the generalization of Kleene' s and Ochmanski's theorems to complex trace languages. (C) 1995 Academ ic Press, Inc.