Proc. CS&P '06 Star-connected rational expressions

Abstract. Star-connected rational expressions were considered only as expressions defining trace languages. In this paper we continue the study of the class of flat languages defined by this kind of rational expressions (see [5], [4]). We obtain stronger results and prove that any language is star-connected iff it is accepted by a finite automaton with cycles which are proper composition of connected cycles. The theory of traces has two independent origins: combinatorial problems and the theory of concurrent systems. Since the fundamental Mazurkiewicz’s paper [6], trace languages are regarded as a powerful means for description of behaviours of concurrent systems. The formal language theory over traces, limited to recognizable and rational trace languages, is the subject of [8]. It is known that rational expressions with classical meaning are useless for expressing recognizable trace languages. For example classical iteration T ⋆ of a recognizable trace language T need not be recognizable. We assume the reader knows basic notions of the theory of free monoids: finite automata, regular expressions (named, from now on, rational expressions) and regular languages. A language L ⊆ A ⋆ is recognizable if it is recognizable by a finite automaton, and is rational if it is defined by a rational expression. The classes Rec of recognizable and Rat of rational subsets are different in all trace monoids which are not free. In spite of this, rational expressions over trace monoids are proved to be quite useful for description of recognizable subsets of arbitrary trace monoids. Namely, in any trace monoid, the class Rec can be characterized with some special kind of rational expressions, called the star-connected rational expressions. By virtue of that fact, the role of rational expressions in trace monoids appears not less important than in free monoids.