Uniform generation in trace monoids

DOI10.1007/978-3-662-48057-1_5MaRDI QIDQ2946325zbMATH OpenOpenAlexFDO

Authors Samy Abbes, Jean Mairesse

Publication date 16 September 2015

Published in Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.02455

zbMATH Keywords

Möbius polynomialtrace monoiduniform generation

Mathematics Subject Classification ID

Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Free semigroups, generators and relations, word problems (20M05)

Abstract: We consider the problem of random uniform generation of traces (the elements of a free partially commutative monoid) in light of the uniform measure on the boundary at infinity of the associated monoid. We obtain a product decomposition of the uniform measure at infinity if the trace monoid has several irreducible components-a case where other notions such as Parry measures, are not defined. Random generation algorithms are then examined.

Recommendations

• Uniform and Bernoulli measures on the boundary of trace monoids
• scientific article; zbMATH DE number 4114058
• APPROXIMATING THE MEAN SPEEDUP IN TRACE MONOIDS
• SOME LIMIT DISTRIBUTIONS IN ANALYSIS OF ALGORITHMS FOR PROBLEMS ON TRACE LANGUAGES
• Computing the average parallelism in trace monoids.

Cites work

• A Course in Enumeration
• A fluid analysis framework for a Markovian process algebra
• An Introduction to Symbolic Dynamics and Coding
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Combinatorial problems of commutation and rearrangements
• Combinatorics on traces
• Enumeration and random generation of concurrent computations
• scientific article; zbMATH DE number 4002104 (Why is no real title available?)
• Intrinsic Markov Chains
• Note on the smallest root of the independence polynomial
• On the foundations of combinatorial theory I. Theory of M�bius Functions
• Projective topology on bifinite domains and applications
• Symbolic dynamics. One-sided, two-sided and countable state Markov shifts
• Uniform and Bernoulli measures on the boundary of trace monoids
• Uniform random generation of decomposable structures using floating-point arithmetic

Cited in

(15)

• Toward uniform random generation in 1-safe Petri nets
• Synchronization of Bernoulli sequences on shared letters
• A quantitative study of fork-join processes with non-deterministic choice: application to the statistical exploration of the state-space
• Markovian dynamics of concurrent systems
• Random walk on a finitely generated monoid
• SOME LIMIT DISTRIBUTIONS IN ANALYSIS OF ALGORITHMS FOR PROBLEMS ON TRACE LANGUAGES
• APPROXIMATING THE MEAN SPEEDUP IN TRACE MONOIDS
• scientific article; zbMATH DE number 2040903 (Why is no real title available?)
• Uniform and Bernoulli measures on the boundary of trace monoids
• Uniform measures on braid monoids and dual braid monoids
• Uniform generation of infinite traces
• Quantitative and algorithmic aspects of barrier synchronization in concurrency
• scientific article; zbMATH DE number 7204953 (Why is no real title available?)
• The Combinatorics of Barrier Synchronization
• A combinatorial study of async/await processes

This page was built for publication: Uniform generation in trace monoids

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