Synchronization of Bernoulli sequences on shared letters

DOI10.1016/J.IC.2017.04.002MaRDI QIDQ2013553zbMATH OpenOpenAlexFDO

Authors Samy Abbes

Publication date 8 August 2017

Published in Information and Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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: The topic of this paper is the distributed and incremental generation of long executions of concurrent systems, uniformly or more generally with weights associated to elementary actions. Synchronizing sequences of letters on alphabets sharing letters are known to produce a trace in the concurrency theoretic sense, i.e., a labeled partially ordered set. We study the probabilistic aspects by considering the synchronization of Bernoulli sequences of letters, under the light of Bernoulli and uniform measures recently introduced for trace monoids. We introduce two algorithms that produce random traces, using only local random primitives. We thoroughly study some specific examples, the path model and the ring model, both of arbitrary size. For these models, we show how to generate any Bernoulli distributed random traces, which includes the case of uniform generation.

Recommendations

• Uniform generation in trace monoids
• Uniform and Bernoulli measures on the boundary of trace monoids
• scientific article; zbMATH DE number 2086409
• SOME LIMIT DISTRIBUTIONS IN ANALYSIS OF ALGORITHMS FOR PROBLEMS ON TRACE LANGUAGES
• On the synchronization of traces

Cites work

• A linear algorithm for the random sampling from regular languages
• Asynchronous Games over Tree Architectures
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• 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.
• scientific article; zbMATH DE number 3897991 (Why is no real title available?)
• scientific article; zbMATH DE number 3970130 (Why is no real title available?)
• scientific article; zbMATH DE number 4002104 (Why is no real title available?)
• scientific article; zbMATH DE number 4030996 (Why is no real title available?)
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• Lectures on Petri nets. 1: Basic models. Advances in Petri nets
• Non-negative matrices and Markov chains. 2nd ed
• Random Walks on Infinite Graphs and Groups
• Uniform and Bernoulli measures on the boundary of trace monoids
• Uniform generation in trace monoids

Cited in

(4)

• Uniform and Bernoulli measures on the boundary of trace monoids
• scientific article; zbMATH DE number 1394287 (Why is no real title available?)
• Uniform generation of infinite traces
• Mixed nondeterministic-probabilistic automata: blending graphical probabilistic models with nondeterminism

This page was built for publication: Synchronization of Bernoulli sequences on shared letters

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