A Kleene iteration for parallelism

. This paper extends automata-theoretic techniques to unbounded parallel behaviour, as seen for instance in Petri nets. Languages are defined to be sets of (labelled) series-parallel posets --- or, equivalently, sets of terms in an algebra with two product operations: sequential and parallel. In an earlier paper, we restricted ourselves to languages of posets having bounded width and introduced a notion of branching automaton. In this paper, we drop the restriction to bounded width. We define rational expressions, a natural generalization of the usual ones over words, and prove a Kleene theorem connecting them to regular languages (accepted by finite branching automata). We also show that recognizable languages (inverse images by a morphism into a finite algebra) are strictly weaker. Introduction The success of automata as a computational model has led to their being generalized in many different ways. Early on, Thatcher and Wright followed an idea of Buchi (as cited in [16]) and co..