Abstract:
Driven by the interest of reasoning about probabilistic programming languages, we set out to study a notion of uniqueness of normal forms for them. To provide a tractable proof method for it, we define a property of distribution confluence which is shown to imply the desired uniqueness (even for infinite sequences of reduction) and further properties. We then carry over several criteria from the classical case, such as Newman's lemma, to simplify proving confluence in concrete languages. Using these criteria, we obtain simple proofs of confluence for λ1, an affine probabilistic λ-calculus, and for Q*, a quantum programming language for which a related property has already been proven in the literature. © 2018 The Author(s)
Registro:
Documento: |
Artículo
|
Título: | Confluence in Probabilistic Rewriting |
Autor: | Díaz-Caro, A.; Martínez, G. |
Filiación: | Universidad Nacional de Quilmes, Roque Sáenz Peña 352, B1876BXD, Bernal, Buenos Aires, Argentina CONICET-Universidad de Buenos Aires, Instituto de Investigación en Ciencias de la Computación, Pabellón 1, Ciudad Universitaria, C1428EGA, Buenos Aires, Argentina CIFASIS-CONICET & Universidad Nacional de Rosario, Ocampo y Esmeralda, S2000EZP, Rosario, Santa Fe, Argentina
|
Palabras clave: | abstract rewriting system; confluence; probabilistic rewriting; Calculations; Computer programming languages; confluence; Lambda calculus; Normal form; Probabilistic programming language; probabilistic rewriting; Proof methods; Quantum programming languages; Rewriting systems; Differentiation (calculus) |
Año: | 2018
|
Volumen: | 338
|
Página de inicio: | 115
|
Página de fin: | 131
|
DOI: |
http://dx.doi.org/10.1016/j.entcs.2018.10.008 |
Título revista: | Electronic Notes in Theoretical Computer Science
|
Título revista abreviado: | Electron. Notes Theor. Comput. Sci.
|
ISSN: | 15710661
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710661_v338_n_p115_DiazCaro |
Referencias:
- Bournez, O., Garnier, F., Proving positive almost-sure termination (2005) Proceedings of the 16th International Conference on Term Rewriting and Applications (RTA'05), Lecture Notes in Computer Science, 3467, pp. 323-337. , J. Giesl
- Bournez, O., Hoyrup, M., Rewriting logic and probabilities (2003) Rewriting Techniques and Applications, Lecture Notes in Computer Science, 2706, pp. 61-75. , R. Nieuwenhuis
- Bournez, O., Kirchner, C., Probabilistic Rewrite Strategies. Applications to ELAN (2002) Proceedings of the 13th International Conference on Rewriting Techniques and Applications (RTA'02), Lecture Notes in Computer Science, 2378, pp. 252-266. , S. Tison
- Church, A., Rosser, J.B., Some properties of conversion (1936) Transactions of the American Mathematical Society, 39, pp. 472-482
- Dal Lago, U., Faggian, C., Valiron, B., Yoshimizu, A., The geometry of parallelism: Classical, probabilistic, and quantum effects (2016); Dal Lago, U., Faggian, C., Valiron, B., Yoshimizu, A., The geometry of parallelism: Classical, probabilistic, and quantum effects (2017) Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL 2017, pp. 833-845. , http://doi.acm.org/10.1145/3009837.3009859, URL
- Dal Lago, U., Masini, A., Zorzi, M., Confluence results for a quantum lambda calculus with measurements extended version of [8]; Dal Lago, U., Masini, A., Zorzi, M., Confluence results for a quantum lambda calculus with measurements (2011) Proceedings of the 6th International Workshop on Quantum Physics and Logic (QPL'09), Electronic Notes in Theoretical Computer Science, vol. 270.2, pp. 251-261. , B. Coecke P. Panangaden P. Selinger
- Dal Lago, U., Zorzi, M., Probabilistic operational semantics for the lambda calculus (2012) RAIRO Theoretical Informatics and Applications, 46, pp. 413-450
- Di Pierro, A., Hankin, C., Wiklicky, H., Probabilistic λ-calculus and quantitative program analysis (2005) Journal of Logic and Computation, 15, pp. 159-179
- Díaz-Caro, A., Arrighi, P., Gadella, M., Grattage, J., Measurements and confluence in quantum lambda calculi with explicit qubits (2011) Proceedings of the Joint 5th International Workshop on Quantum Physics and Logic and 4th Workshop on Developments in Computational Models (QPL/DCM'08), Electronic Notes in Theoretical Computer Science, vol. 270.1, pp. 59-74. , B. Coecke I. Mackie P. Panangaden P. Selinger
- Gordon, A., Henzinger, T.A., Nori, A., Rajamani, S., Probabilistic programming (2014) Proceedings of the 36th International Conference on Software Engineering. Session on Future of Software Engineering, FOSE'14, pp. 167-181. , J. Herbsleb
- Huet, G., Confluent reductions: Abstract properties and applications to term rewriting systems: Abstract properties and applications to term rewriting systems (1980) Journal of the ACM, 27, pp. 797-821
- Jouannaud, J.-P., Kirchner, H., Completion of a set of rules modulo a set of equations (1984) Proceedings of the 11th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL '84, pp. 83-92
- Kirkeby, M., Christiansen, H., Confluence and convergence in probabilistically terminating reduction systems (2017) Proceedings of the 27th International Symposium on Logic-Based Program Synthesis and Transformation, LOPSTR '17, pp. 33-46
- Kozen, D., Semantics of probabilistic programs (1981) Journal of Computer and System Sciences, 22, pp. 328-350
- Martínez, G., Confluencia en sistemas de reescritura probabilista (2017), https://dcc.fceia.unr.edu.ar/~gmartinez/tesina, Master's thesis Universidad Nacional de Rosario Argentina available at; Newman, M.H.A., On theories with a combinatorial definition of “equivalence” (1942) Annals of Mathematics, 43, pp. 223-243
- Pati, A.K., Braunstein, S.L., Impossibility of deleting an unknown quantum state (2000) Nature, 404, pp. 164-165
- Peterson, G.E., Stickel, M.E., Complete sets of reductions for some equational theories (1981) Journal of the ACM, 28, pp. 233-264
- Plotkin, G.D., Call-by-name, call-by-value and the λ-calculus (1975) Theoretical Computer Science, 1, pp. 125-159
- Selinger, P., Valiron, B., A lambda calculus for quantum computation with classical control (2005) Proceedings of the 7th International Conference on Typed Lambda Calculi and Applications (TLCA'05), Lecture Notes in Computer Science, 3461, pp. 354-368. , P. Urzyczyn
- Simpson, A., Reduction in a linear lambda-calculus with applications to operational semantics (2005) Proceedings of the 16th International Conference on Term Rewriting and Applications (RTA'05), Lecture Notes in Computer Science, 3467, pp. 219-234. , J. Giesl
- van Tonder, A., A lambda calculus for quantum computation (2004) SIAM Journal on Computing, 33, pp. 1109-1135
- Wootters, W.K., Zurek, W.H., A single quantum cannot be cloned (1982) Nature, 299, pp. 802-803
Citas:
---------- APA ----------
Díaz-Caro, A. & Martínez, G.
(2018)
. Confluence in Probabilistic Rewriting. Electronic Notes in Theoretical Computer Science, 338, 115-131.
http://dx.doi.org/10.1016/j.entcs.2018.10.008---------- CHICAGO ----------
Díaz-Caro, A., Martínez, G.
"Confluence in Probabilistic Rewriting"
. Electronic Notes in Theoretical Computer Science 338
(2018) : 115-131.
http://dx.doi.org/10.1016/j.entcs.2018.10.008---------- MLA ----------
Díaz-Caro, A., Martínez, G.
"Confluence in Probabilistic Rewriting"
. Electronic Notes in Theoretical Computer Science, vol. 338, 2018, pp. 115-131.
http://dx.doi.org/10.1016/j.entcs.2018.10.008---------- VANCOUVER ----------
Díaz-Caro, A., Martínez, G. Confluence in Probabilistic Rewriting. Electron. Notes Theor. Comput. Sci. 2018;338:115-131.
http://dx.doi.org/10.1016/j.entcs.2018.10.008