Methods for computing the concurrency degree of commutation monoids
Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Computational methods in Markov chains (60J22) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)
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].
- Complexity results on the conjugacy problem for monoids
- Computing the average parallelism in trace monoids.
- Concurrency measure in commutation monoids
- Two optimal parallel algorithms on the commutation class of a word
- Approximability and Non-approximability Results in Computing the Mean Speedup of Trace Monoids
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)