Abstract
The aim of this work is to define a useful concurrency measure, easy to implement and whose computation complexity allows the study of real examples. We extend the measure introduced in [BT87] to a probabilistic one, by means of a natural translation of the synchronized automata of Arnold-Nivat's model to Markov chains: the computation of the measure uses the concept of average time before absorbtion. Some examples including the mutual exclusion are detailed.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J.M.Autebert "Langages algébriques" Masson, 1987
A.Arnold-M.Nivat "Comportements de processus" Rapport interne L.I.T.P. no 82-12
M.Ben Ari "Processus concurrents-Introduction à la programmation parallèle" Masson 1986
J.Beauquier-B.Bérard-L.Thimonier "On a concurrency measure" Rapport interne L.R.I. no 306, Octobre 1986
E.A. Bender "Asymptotic methods in enumeration" S.I.A.M. review, vol. 16, no 4, pp 485–515, october 1974
J. Berstel-C. Reutenauer "Les séries ratinnelles et leurs languages" Collection Etudes et recherches en Informatique, Masson, Paris 1984
B. Bérard-L. Thimonier "On a concurrency measure" 2nd I.S.C.I.S. proceeding, Istanbul 1987, Nova Science Publishers, New York, pp 211–225
W.Feller "An introduction to probability theory", vol.1, 2. Addison-Wesley, 1968
P.Flajolet "Analyse d'algorithmes de manipulation d'arbres et de fichiers" B.U.R.O. cahiers 34–35, 1981
J.Françon "A quantitative approach of mutual exclusion" R.A.I.R.O. theoretical Informatics and Applications no 20, 1986, pp 275–289
P. Flajolet-D. Gardy-L. Thimonier "Random allocations and probabilistic languages" 15th I.C.A.L.P. proc., L.N.C.S. 317, pp 239–253, 1988
J.Françon-B.Randrianarimanana-R.Schott "Dynamic data structures with finite population: a combinatorial analysis" F.C.T.'89 proc., L.N.C.S. 380, pp 162–174
D.Geniet "Automaf: un système de construction d'automates synchronisés et de calcul de mesure du parallélisme" Thèse, Université Paris XI, 1989
D.Geniet "Compacting and synchronizing non-deterministic finite automata with Automaf" 4th I.S.C.I.S. proc., Cesme 1989, Turkey, to appear
D.Geniet-L.Thimonier "Using generating functions to compute concurrency" FCT'89 proc., L.N.C.S. 380, pp 185–196
M. Molloy "Performance analysis using stochastic Petri nets" I.E.E.E. Transactions on computers, vol. C-31, no 9, sept. 1982, pp 913–917
A. Paz "Introduction to probabilistic automata" Academic Press, New York-London 1971
C.Pair-R.Mohr-R.Schott "Construire les algorithmes" Dunod informatique 1988
L.Thimonier "Generating functions and random words" Abstract in the bulletin of E.A.T.C.S. no 36, october 1988, pp 406–408 Doctoral dissertation, Université Paris XI, 1988
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Geniet, D., Schott, R., Thimonier, L. (1990). A markovian concurrency measure. In: Arnold, A. (eds) CAAP '90. CAAP 1990. Lecture Notes in Computer Science, vol 431. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-52590-4_48
Download citation
DOI: https://doi.org/10.1007/3-540-52590-4_48
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-52590-5
Online ISBN: 978-3-540-47042-7
eBook Packages: Springer Book Archive