Traces are used to model the occurrence of events in concurrent systems [
9]. Roughly speaking, a letter corresponds to an event and two letters commute when the corresponding events can occur simultaneously.
In this context, the two basic performance measures associated with a trace
t are its
length ∣
t∣ (the ‘sequential’ execution time) and its
height
h(
t) (the ‘parallel’ execution time). The ratio ∣
t∣/
h(
t) captures in some sense the
amount of parallelism (the
speedup in [
6]). Let
$
\mathbb{M}
$
\mathbb{M}
be a trace monoid. Define the generating series
|
$
F = \sum\limits_{t \in \mathbb{M}} {x^{h(t)} y^{\left| t \right|} } ,L = \sum\limits_{t \in \mathbb{M}} {y^{\left| t \right|} } ,H = \sum\limits_{t \in \mathbb{M}} {x^{h(t)} } .
$
F = \sum\limits_{t \in \mathbb{M}} {x^{h(t)} y^{\left| t \right|} } ,L = \sum\limits_{t \in \mathbb{M}} {y^{\left| t \right|} } ,H = \sum\limits_{t \in \mathbb{M}} {x^{h(t)} } .
|
((1)) |
It is well known that L is a rational series [5]. We prove that F and H are also rational and we provide finite representations for the series. Exploiting the symmetries of the trace monoid enables
to obtain representations of reduced dimensions. We use the rationality to obtain precise information on the asymptotics of
the number of traces of a given height or length.
This work was partially supported by the European Community Framework IV programme through the research network ALAPEDES.