Number of Prefixes in Trace Monoids: Clique Polynomials and Dependency Graphs

We present some asymptotic properties on the average number of prefixes in trace languages. Such languages are characterized by an alphabet and a set of commutation rules, also called concurrent alphabet, which can be encoded by an independency graph or by its complement, called dependency graph. One key technical result, which has its own interest, concerns general properties of graphs and states that “if an undirected graph admits a transitive orientation, then the multiplicity of the root of minimum modulus of its clique polynomial is smaller or equal to the number of connected components of its complement graph”. As a consequence, under the same hypothesis of transitive orientation of the independency graph, one obtains the relation E[Tn] = O(E[Wn]), where the random variables Tn and Wn represent the number of prefixes in traces of length n under two different fundamental probabilistic models: – the uniform distribution among traces of length n (for Tn), – the uniform distribution among words of length n (for Wn). These two quantities are related to the time complexity of algorithms for solving classical membership problems on trace languages.