×
Kozen, Dexter

Semantics of probabilistic programs. (English) Zbl 0476.68019

J. Comput. Syst. Sci. 22, 328-350 (1981).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0476.68019

Cited in 2 Reviews
Cited in 114 Documents

MSC:

68Q60 Specification and verification (program logics, model checking, etc.)
68N01 General topics in the theory of software

Keywords:

semantics for a high level probabilistic programming language; programs as partial measurable functions on a measurable space; programs as continuous linear operators on a Banach space of measures; ordered domains; action on fixed inputs
Cite Review PDF
Full Text: DOI

References:

[1] Adleman, L., Two theorems on random polynomial time, (Proceedings, 19th Symposium on Foundation of Computer Science. Proceedings, 19th Symposium on Foundation of Computer Science, Ann Arbor (1978)), 75-83
[2] Backus, J., The Fortran automatic coding system, (Proceedings, Western Joint Computer Conf.. Proceedings, Western Joint Computer Conf., Los Angeles (1957)), 188-198
[3] Birkhoff, G., Dependent probabilities and the spaces \((L)\), (Proc. N.A.S., 24 (1938)), 154-159 · JFM 64.0535.01
[4] Birkhoff, G., Lattice Theory, (Amer. Math. Soc. Colloquium Publications, Vol. 25 (1967)), Providence, R. I. · Zbl 0126.03801
[5] Chung, K. L., A Course in Probability Theory (1974), Academic Press: Academic Press New York · Zbl 0159.45701
[6] Collatz, L., Functional Analysis and Numerical Mathematics (1966), Academic Press: Academic Press New York · Zbl 0221.65088
[7] Dunford, N.; Schwartz, J., (Linear Operators, Vol. 1 (1958), Interscience: Interscience New York) · Zbl 0084.10402
[8] Feller, W., (An Introduction to Probability Theory and Its Applications, Vol. 1 (1968), Wiley: Wiley New York) · Zbl 0155.23101
[9] Floyd, R.; Rivest, R., Expected time for selection, Comm. Assoc. Comput. Mach., 18, 165-172 (1975) · Zbl 0296.68049
[10] Gill, J., Computational complexity of probabilistic Turing machines, (Proceedings, 6th ACM Symposium on Theory of Computing (1974)), 91-95 · Zbl 0357.68056
[11] Gouda, M.; Manning, E., Probabilistic cost machines, (Traub, J. F., Algorithms and Complexity (1976), Academic Press: Academic Press New York), 462
[12] Halmos, P., Measure Theory (1950), Van Nostrand: Van Nostrand New York · Zbl 0040.16802
[13] Kakutani, S., Concrete representation of abstract \((L)\)-spaces and the mean ergodic theorem, Ann. of Math., 42, 523-537 (1941) · JFM 67.0419.01
[14] Karp, R., Probabilistic analysis of combinatorial search, (Traub, J. F., Algorithms and Complexity (1976), Academic Press: Academic Press New York), 1-20
[15] Knuth, D., (Art of Computer Programming: Sorting and Searching, Vol. 3 (1973), Addison-Wesley: Addison-Wesley Reading, Mass) · Zbl 0302.68010
[16] Kurtz, T. E., SIGPLAN Notices, 13, 8, 103-118 (1978)
[17] Lehmann, D., Categories for fixpoint semantics, (Proceedings, 17th IEEE Symposium on Foundations of Computer Science (1976)), 122-126
[18] Manna, Z., Mathematical Theory of Computation (1974), McGraw-Hill: McGraw-Hill New York · Zbl 0353.68066
[19] Miller, G., Riemann’s hypothesis and tests for primality, (Proceedings, 7th ACM Symposium on Theory of Computing (1975)), 234-239 · Zbl 0365.68052
[20] Paz, A., Introduction to Probabilistic Automata (1971), Academic Press: Academic Press New York · Zbl 0234.94055
[21] Plotkin, G., A powerdomain construction, SIAM J. Comput., 5, 452-487 (1976) · Zbl 0355.68015
[22] Rabin, M. O., Probabilistic algorithms, (Traub, J. F., Algorithms and Complexity (1976), Academic Press: Academic Press New York), 21-40 · Zbl 0384.60001
[23] Ramshaw, L. H., Formalizing the Analysis of Algorithms, (Ph. D. Thesis (1979), Computer Science, Stanford University)
[24] Scott, D., Outline of a mathematical theory of computation, (Proceedings, 4th Princeton Conf. on Info. Sci. and Sys. (1970), Princeton), 169-176
[25] Scott, D.; Strachey, C., Towards a mathematical semanties for computer languages, (Tech. mono. PRC6 (1971), Oxford Univ)
[26] Solovay, R.; Strassen, V., Fast Monte Carlo tests for primality, SIAM J. Comput., 684-685 (1977) · Zbl 0345.10002
[27] Vuillemin, J., Proof Techniques for Recursive Programs, (Ph.D. thesis (1973), Stanford University)
[28] Yao, A., Probabilistic computations: toward a unified measure of complexity, (Proceedings, 18th IEEE Symp. on foundations of Computer Science (1977), Providence), 222-227
[29] Yao, A.; Yao, F., On the average case complexity of selecting the kth best, (Proceedings, 19th IEEE Symp. on Foundations of Computer Science. Proceedings, 19th IEEE Symp. on Foundations of Computer Science, Ann Arbor (1978)), 180-289
[30] Zeiger, H. P., Formal models for some features of programming languages, (Proceedings, 1st ACM Symposium on Theory of Computing (1969), Marina del Rey: Marina del Rey Calif), 211-215 · Zbl 1282.68090
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.