Methods for computing the concurrency degree of commutation monoids

From MaRDI portal





Let \(A\) be a finite alphabet and \(\theta\) be a symmetric and irreflexive relation on \(A\). The quotient monoid \(A^{*}/ \cong\) of \(A^{*}\) by the least congruence \(\cong\) containing \(\theta\) is called a commutation monoid (or a partial commutative monoid). Commutation monoids model concurrent processes. For a word \(w\) over \(A\), let \(\text{dep}(w)\) denote the number of factors in the Foata normal form of \(w\) with respect to \((A,\theta)\) and set \(d(w)=\frac {|w|}{\text{ dep}(w)}\). For every natural number \(n\), let \(w_n\) be a uniformly and randomly chosen word of length \(n\), then there exists a number, it is denoted by \(DEG\), such that \(\lim_{n\to\infty}d(w_n)=DEG\) with probability \(1\). The number \(D EG\) is called a concurrency degree of \((A,\theta)\). New methods computing or approximating concurrency degree by Markov chains and random walk are introduced. The connection with problems of Statistical Physics is discussed. For the entire collection see [Zbl 0941.00013].











This page was built for publication: Methods for computing the concurrency degree of commutation monoids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4502595)