Artículo

Díaz-Caro, A.; Martínez, G. "Confluence in Probabilistic Rewriting" (2018) Electronic Notes in Theoretical Computer Science. 338:115-131
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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