Probabilistic estimation of the number of prefixes of a trace

We present a generating function technique to evaluate the number of strings of a given length recognized by a particular kind of finite-state automaton. Using the method we determine some asymptotic estimations of the number of prefixes in free partially commutative monoids. More precisely, we prove that for every concurrent alphabet 〈Σ, C〉, assuming equiprobable strings, all of length n, the average number of prefixes of a trace of length n is ηnk+O(nk-1) and its variance is O(n2k-1), where k is the number of components of the dependency graph 〈Σ, Cc〉 and η is a rational constant depending only on 〈Σ, C〉. These combinatorial results allow to determine the probabilistic behaviour of some algorithms for problems on trace languages, including the Membership Problems for regular and context-free trace languages.