Markovian dynamics of concurrent systems
From MaRDI portal
Publication:2177775
concurrent systemsMarkov chainmonoid actionPetri netsprobabilistic dynamicstrace monoidsuniform measure
Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Abstract: Monoid actions of trace monoids over finite sets are powerful models of concurrent systems---for instance they encompass the class of 1-safe Petri nets. We characterise Markov measures attached to concurrent systems by finitely many parameters with suitable normalisation conditions. These conditions involve polynomials related to the combinatorics of the monoid and of the monoid action. These parameters generalise to concurrent systems the coefficients of the transition matrix of a Markov chain. A natural problem is the existence of the uniform measure for every concurrent system. We prove this existence under an irreducibility condition. The uniform measure of a concurrent system is characterised by a real number, the characteristic root of the action, and a function of pairs of states, the Parry cocyle. A new combinatorial inversion formula allows to identify a polynomial of which the characteristic root is the smallest positive root. Examples based on simple combinatorial tilings are studied.
Recommendations
Cites work
- An Introduction to Symbolic Dynamics and Coding
- Arctic circles, domino tilings and square Young tableaux
- Clique polynomials have a unique root of smallest modulus
- Combinatorial problems of commutation and rearrangements
- Combinatorics on traces
- Computing the average parallelism in trace monoids.
- Continuous Lattices and Domains
- D-completions and the \(d\)-topology
- Empilements de segments et q-énumération de polyominos convexes dirigés. (Heaps of segments and q-enumeration of directed convex polyominoes)
- Free Choice Petri Nets
- scientific article; zbMATH DE number 3885321 (Why is no real title available?)
- scientific article; zbMATH DE number 4002104 (Why is no real title available?)
- scientific article; zbMATH DE number 627763 (Why is no real title available?)
- scientific article; zbMATH DE number 1033382 (Why is no real title available?)
- scientific article; zbMATH DE number 765034 (Why is no real title available?)
- scientific article; zbMATH DE number 898018 (Why is no real title available?)
- Intrinsic Markov Chains
- Non-negative matrices and Markov chains. 2nd ed
- Note on the smallest root of the independence polynomial
- On countable completions of quotient ordered semigroups
- On the definition of a family of automata
- On the foundations of combinatorial theory I. Theory of M�bius Functions
- Projective topology on bifinite domains and applications
- Statistical properties of locally free groups with applications to braid groups and growth of random heaps
- Symbolic dynamics. One-sided, two-sided and countable state Markov shifts
- Toward uniform random generation in 1-safe Petri nets
- Uniform and Bernoulli measures on the boundary of trace monoids
- Uniform generation in trace monoids
- Uniform measures on braid monoids and dual braid monoids
Cited in
(7)- A spectral property for concurrent systems and some probabilistic applications
- Deterministic concurrent systems
- scientific article; zbMATH DE number 125889 (Why is no real title available?)
- Uniform and Bernoulli measures on the boundary of trace monoids
- Introduction to Probabilistic Concurrent Systems
- Mixed nondeterministic-probabilistic automata: blending graphical probabilistic models with nondeterminism
- Ergodic properties of concurrent systems
This page was built for publication: Markovian dynamics of concurrent systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2177775)
