Geodesic
Enumeration and Random Generation of Concurrent Computations
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) (2012).

Voir la notice de l'article provenant de la source Episciences

In this paper, we study the shuffle operator on concurrent processes (represented as trees) using analytic combinatorics tools. As a first result, we show that the mean width of shuffle trees is exponentially smaller than the worst case upper-bound. We also study the expected size (in total number of nodes) of shuffle trees. We notice, rather unexpectedly, that only a small ratio of all nodes do not belong to the last two levels. We also provide a precise characterization of what ``exponential growth'' means in the case of the shuffle on trees. Two practical outcomes of our quantitative study are presented: (1) a linear-time algorithm to compute the probability of a concurrent run prefix, and (2) an efficient algorithm for uniform random generation of concurrent runs. 
@article{DMTCS_2012_special_262_a7,
     author = {Bodini, Olivier and Genitrini, Antoine and Peschanski, Fr\'ed\'eric},
     title = {Enumeration and {Random} {Generation} of {Concurrent} {Computations}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)},
     year = {2012},
     doi = {10.46298/dmtcs.2986},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2986/}
}
TY  - JOUR
AU  - Bodini, Olivier
AU  - Genitrini, Antoine
AU  - Peschanski, Frédéric
TI  - Enumeration and Random Generation of Concurrent Computations
JO  - Discrete mathematics & theoretical computer science
PY  - 2012
VL  - DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2986/
DO  - 10.46298/dmtcs.2986
LA  - en
ID  - DMTCS_2012_special_262_a7
ER  - 
%0 Journal Article
%A Bodini, Olivier
%A Genitrini, Antoine
%A Peschanski, Frédéric
%T Enumeration and Random Generation of Concurrent Computations
%J Discrete mathematics & theoretical computer science
%D 2012
%V DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2986/
%R 10.46298/dmtcs.2986
%G en
%F DMTCS_2012_special_262_a7
Bodini, Olivier; Genitrini, Antoine; Peschanski, Frédéric. Enumeration and Random Generation of Concurrent Computations. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) (2012). doi : 10.46298/dmtcs.2986. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2986/

Cité par Sources :