Abstract
In order to extend the modeling capabilities of rewriting systems, it is rather natural to consider that the firing of rules can be subject to some probabilistic laws. Considering rewrite rules subject to probabilities leads to numerous questions about the underlying notions and results.
We focus here on the problem of termination of a set of probabilistic rewrite rules. A probabilistic rewrite system is said almost surely terminating if the probability that a derivation leads to a normal form is one. Such a system is said positively almost surely terminating if furthermore the mean length of a derivation is finite. We provide several results and techniques in order to prove positive almost sure termination of a given set of probabilistic rewrite rules. All these techniques subsume classical ones for non-probabilistic systems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baader, F., Nipkow, T.: Term Rewriting and All That. Cambridge University Press, Cambridge (1998)
Balbo, G.: Introduction to Stochastic Petri nets. In: Brinksma, E., Hermanns, H., Katoen, J.-P. (eds.) EEF School 2000 and FMPA 2000. LNCS, vol. 2090, p. 84. Springer, Heidelberg (2001)
Bournez, O., Hoyrup, M.: Rewriting Logic and Probabilities. In: Nieuwenhuis, R. (ed.) RTA 2003. LNCS, vol. 2706, pp. 61–75. Springer, Heidelberg (2003)
Bournez, O., Kirchner, C.: Probabilistic Rewrite Strategies: Applications to ELAN. In: Tison, S. (ed.) RTA 2002. LNCS, vol. 2378, pp. 252–266. Springer, Heidelberg (2002)
Brémaud, P.: Markov Chains, Gibbs Fields, Monte Carlo Simulation, and Queues. Springer, New York (2001)
de Alfaro, L.: Formal Verification of Probabilistic Systems. PhD thesis, Stanford University (1997)
Feller, W.: An Introduction to Probability Theory and its Applications, vol. 1. Wiley, Chichester (1968)
Foster, F.G.: On the Stochastic Matrices Associated with Certain Queuing Processes. The Annals of Mathematical Statistics 24, 355–360 (1953)
Frühwirth, T., Di Pierro, A., Wiklicky, H.: Toward Probabilistic Constraint Handling Rules. In: Abdennadher, S., Frühwirth, T. (eds.) RCoRP 2001 (2001)
Grimmett, G.: Probability Theory. Cambridge University Press, Cambridge (1993)
Hansson, H.: Time and Probability in Formal Design of Distributed Systems. Series in Real-Time Safety Critical Systems. Elsevier, Amsterdam (1994)
Jones, C.: Probabilistic Non-determinism. PhD thesis, University of Edinburgh (1990)
Klop, J.W.: Term Rewriting Systems. In: Abramsky, S., Gabbay, D.M., Maibaum, T.S.E. (eds.) Handbook of Logic in Computer Science, vol. 2, ch. 1, pp. 1–117. Oxford University Press, Oxford (1992)
Kwiatkowska, M., Norman, G., Parker, D.: PRISM: Probabilistic Symbolic Model Checker. In: Field, T., Harrison, P.G., Bradley, J., Harder, U. (eds.) TOOLS 2002. LNCS, vol. 2324, p. 200. Springer, Heidelberg (2002)
Lynch, N.: Distributed Algorithms. Morgan Kaufmann Publishers, Inc., San Francisco (1997)
Martí-Oliet, N., Meseguer, J.: Rewriting Logic: Roadmap and Bibliography. Theoretical Computer Science 285(2), 121–154 (2002)
Meseguer, J.: Conditional Rewriting Logic as a Unified Model of Concurrency. Theoretical Computer Science 96(1), 73–155 (1992)
Nirman, K., Sen, K., Meseguer, J., Agha, G.: A Rewriting Based Model for Probabilistic Distributed Object Systems. In: Najm, E., Nestmann, U., Stevens, P. (eds.) FMOODS 2003. LNCS, vol. 2884, pp. 32–46. Springer, Heidelberg (2003)
Panangaden: Does Combining Probability and Non-Determinism Makes Sense? Bulletin of the EATCS (2001)
Puternam, M.L.: Markov Decision Processes - Discrete Stochastic Dynamic Programming. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, Chichester (1994)
Rudin, W.: Real and Complex Analysis, 3rd edn. McGraw-Hill, USA (1987)
Sanders, W.H., Meyer, J.F.: Stochastic Activity Networks: Formal Definitions and Concepts. In: Brinksma, E., Hermanns, H., Katoen, J.-P. (eds.) EEF School 2000 and FMPA 2000. LNCS, vol. 2090, p. 315. Springer, Heidelberg (2001)
Schneider, M.: Self-stabilization. ACM Computing Surveys 25, 45–67 (1993)
Segala, R., Lynch, N.: Probabilistic Simulations for Probabilistic Processes. In: Jonsson, B., Parrow, J. (eds.) CONCUR 1994. LNCS, vol. 836, p. 481. Springer, Heidelberg (1994)
van Glabbeek, R., Smolka, S.A., Steffen, B., Tofts, C.M.N.: Reactive, Generative, and Stratified Models of Probabilistic Processes. In: LICS 1990, pp. 130–141. IEEE Computer Society Press, Los Alamitos (1990)
Vardi, M.Y.: Automatic Verification of Probabilistic Concurrent Finite-State Programs. In: FOCS 1985, pp. 327–338 (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bournez, O., Garnier, F. (2005). Proving Positive Almost-Sure Termination. In: Giesl, J. (eds) Term Rewriting and Applications. RTA 2005. Lecture Notes in Computer Science, vol 3467. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-32033-3_24
Download citation
DOI: https://doi.org/10.1007/978-3-540-32033-3_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25596-3
Online ISBN: 978-3-540-32033-3
eBook Packages: Computer ScienceComputer Science (R0)