Abstract
We investigate notions of observable behaviour of programs which include quantitative aspects of computation along with the most commonly assumed qualitative ones. We model these notions by means of a transition system where transitions occur with a given probability and an associated ‘cost’ expressing some complexity measure (e.g. running time or, in general, resources consumption).
The addition of these quantities allows for a natural formulation of the average behaviour of a program, whose specification and analysis is particularly important in the study of system performance and reliability. It also allows for an average-case analysis of programs’ complexity, which can be seen as a semantical counterpart of the average-case asymptotic analysis of algorithms.
We base our model on the Concurrent Constraint Programming (CCP) paradigm and we argue that it can be an appropriate base for further developments oriented to the analysis and verification of average properties.
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
Emile Aarts and Jan Korst. Simulated Annealing and Boltzmann Machines. John Wiley & Sons, Chicester, 1989.
Nicos Angelopoulos, Alessandra di Pierro, and Herbert Wiklicky. Implementing randomised algorithms in constraint logic programming. In JICSLP’98-Joint International Conference and Symposium on Logic Programming, Cambridge, Massachusetts-London, England, 1998. MIT Press.
Marco Bernardo. Theory and Application of Extended Markovian Process Algebra. PhD thesis, University of Bologna, Bologna, February 1999.
Marco Bernardo and Roberto Gorrieri. A tutorial on EMPA: A theory of concurrent processes with nondeterminism, priorities, probabilities and time. Technical Report UBLCS-96-17, Department of Computer Science, University of Bologna, January 1997.
Madhu D.K. Bhabuta. Quantitative Analysis of ATM Networks. PhD thesis, Imperial College, University of London, London, August 1998.
Stefano Bistarelli, Phillipe Codognet, Yan Georget, and Francessca Rossi. Abstracting soft constraint. In K.R. Apt, T. Kakas, E. Monfroy, and F. Rossi, (editors), Proceedings of the ERCIM/COMPULOG Workshop on Constraints, Pahos, Cyprus, 1999.
Stefano Bistarelli, Ugo Montanari, and Francesca Rossi. Semiring-based constraint satisfaction and optimization. Journal of the ACM, 44(2):201–236, 1997.
Patrick Cousot and Radhia Cousot. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In Proceedings of POPL’77-4th Symposium on Principles of Programming Languages, Los Angeles, CA, pages 238–252, January 1977.
Luca de Alfaro. Formal Verification of Probabilistic Systems. PhD thesis, Stanford University, December 1997.
Luca de Alfaro. How to Specify and Verify the Long-Run Average Behavior of Probabilistic Systems. In Procceedings of LICS’98-13th Symposium on Logic in Computer Science, pages 174–183, Indianapolis, 1998. IEEE Computer Society Press.
Frank S. de Boer, M. Gabbrielli, E. Marchiori, and Catuscia Palamidessi. Proving Concurrent Constraint Programs Correct. ACM Transactions on Programming Languages and Systems, 1997.
Frank S. de Boer and Catuscia Palamidessi. A fully abstract model for concurrent constraint programming. In S. Abramsky and T.S.E. Maibaum, (editors), Proceedings of TAPSOFT/CAAP, volume 493 of Lecture Notes in Computer Science, pages 296–319. Springer-Verlag, 1991.
Alessandra di Pierro and Herbert Wiklicky. An Operational Semantics for Probabilistic Concurrent Constraint Programming. In Y. Choo, P. Iyer and D. Schmidt, (editors), Proceedings of ICCL’ 98-International Conference on Computer Languages, IEEE Computer Society and ACM SIGPLAN, pages 174–183, Chicago, 1998.
Alessandra di Pierro and Herbert Wiklicky. Probabilistic Concurrent Constraint Programming: Towards a fully abstract model. In L. Brim, J. Gruska, and J. Zlatuska, (editors), Proceedings of MFCS’98-Mathematical Foundations of Computer Science, volume 1450 of Lecture Notes in Computer Science, pages 446–455, Berlin-New York, August 1998. Springer Verlag.
Alessandra di Pierro and Herbert Wiklicky. Ergodic average in constraint programming. In Marta Kwiatkowska, (editor), Proceedings of PROBMIV’99-2nd International Workshop on Probabilistic Methods in Verification, number CSR-99-8, pages 49–56, Eindhoven, 1999. University of Birmingham.
D. Ferrari. Computer Systems Performance Evaluation. Prentice-Hall, 1978.
Riccardo Focardi. Analysis and Automatic Detection of Information Flows in Systems and Networks. PhD thesis, University of Bologna, Bologna, November 1998.
David E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, Massachusetts, 1989.
Norbert Götz, Ulrich Herzog, and Michael Rettelbach. TIPP — introduction and application to protocol performance analysis. In H. König, (editor), Formale Beschreibungstechniken für verteilte Systeme, FOKUS. Saur Verlag, 1993.
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, Reading, Massachusetts, 1989.
Guido Grandi. Letter to Leibniz (July 1713). In Leibnizens mathematische Schriften, volume 4.
Geoffrey R. Grimmett and D.R. Stirzaker. Probability and Random Processes. Clarendon Press, Oxford, second edition, 1992.
Charles M. Grinstead and J. Laurie Snell. Introduction to Probability American Mathematical Society, Providence, Rhode Island, second revised edition, 1997.
Vineet Gupta, Radha Jagadeesan, and Vijay A. Saraswat. Probabilistic concurrent constraint programming. In Proceedings of CONCUR’97. Springer Verlag, 1997.
Vintee Gupta, Radha Jagadeesan, and Prakash Panangaden. Stochastic programs as concurrent constraint programs. In Proceedings of POPL’ 99 — 26th Symposium on Principles of Programming Languages, pages 189–202, 1999.
G.W. Hamilton. Usage counting analysis for lazy functional languages. Information and Computation, 146:100–137, 1998.
P.G. Harrison and N.M. Patel. Performance Analysis of Communication Networks and Computer Architectures. Addison-Wesley, 1992.
Dorit S. Hochbaum, (editor). Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, Boston, Massachusetts, 1997.
D. E. Knuth. The Art of Computer Programming, Vol.3: Sorting and Searching. Addison-Wesley, 1998. 2nd edition.
Dexter Kozen. Semantics for probabilistic programs. Journal of Computer and System Sciences, 22:328–350, 1981.
Patrick D. Lincoln, John C. Mitchell, and Andre Scedrov. Stochastic interaction and Linear Logic. In J.-Y. Girard, Y. Lafont, and L. Regnier, editors, Advances in Linear Logic, volume 222 of London Mathematical Society Lecture Note Series, pages 147–166. Cambridge University Press, Cambridge, 1995.
Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, Cambridge, England, 1995.
Jane Hillstone Marina Ribaud. Stochastic process algebras: A new approach to performance modeling. In K. Bagchi and G. Zobrist, (editors), Modeling and Simulation of Advanced Computer Systems. Gordon Breach, London, 1998.
N. Saheb-Djahromi. CPO’s of measures for nondeterminism. Theoretical Computer Science, 12:19–37, 1980.
David Sands. Calculi for Time Analysis of Functional Programs. PhD thesis, Imperial College, University of London, London, September 1990.
Vijay A. Saraswat and Martin Rinard. Concurrent constraint programming. In Proceedings of POPL’ 90-Symposium on Principles of Programming Languages, pages 232–245. ACM, 1990.
Vijay A. Saraswat, Martin Rinard, and Prakash Panangaden. Semantics foundations of concurrent constraint programming. In Proceedings of POPL’ 91-Symposium on Principles of Programming Languages, pages 333–353, 1991.
Roberto Segala. Modelling and Verification of Randomized Distributed Real-Time Systems. PhD thesis, Massachusetts Institute of Technology, June 1995.
Eugene Seneta. Non-negative Matrices and Markov Chains. Springer Verlag, New York-Heidelberg-Berlin, second edition, 1981.
Henk C. Tijms. Stochastic Models-An Algorithmic Approach. John Wiley & Sons, Chichester, 1994.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pierro, A.D., Wiklicky, H. (2000). Quantitative Observables and Averages in Probabilistic Constraint Programming. In: Apt, K.R., Monfroy, E., Kakas, A.C., Rossi, F. (eds) New Trends in Constraints. WC 1999. Lecture Notes in Computer Science(), vol 1865. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44654-0_11
Download citation
DOI: https://doi.org/10.1007/3-540-44654-0_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67885-4
Online ISBN: 978-3-540-44654-5
eBook Packages: Springer Book Archive