License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSCD.2019.19
URN: urn:nbn:de:0030-drops-105263
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10526/
Go to the corresponding LIPIcs Volume Portal

Faggian, Claudia

Probabilistic Rewriting: Normalization, Termination, and Unique Normal Forms

pdf-format:
LIPIcs-FSCD-2019-19.pdf (1 MB)

Abstract

While a mature body of work supports the study of rewriting systems, abstract tools for Probabilistic Rewriting are still limited. We study in this setting questions such as uniqueness of the result (unique limit distribution) and normalizing strategies (is there a strategy to find a result with greatest probability?). The goal is to have tools to analyse the operational properties of probabilistic calculi (such as probabilistic lambda-calculi) whose evaluation is also non-deterministic, in the sense that different reductions are possible.

BibTeX - Entry

@InProceedings{faggian:LIPIcs:2019:10526,
  author =	{Claudia Faggian},
  title =	{{Probabilistic Rewriting: Normalization, Termination, and Unique Normal Forms}},
  booktitle =	{4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019)},
  pages =	{19:1--19:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-107-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{131},
  editor =	{Herman Geuvers},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10526},
  URN =		{urn:nbn:de:0030-drops-105263},
  doi =		{10.4230/LIPIcs.FSCD.2019.19},
  annote =	{Keywords: probabilistic rewriting, PARS, abstract rewriting systems, confluence, probabilistic lambda calculus}
}

Keywords: probabilistic rewriting, PARS, abstract rewriting systems, confluence, probabilistic lambda calculus
Collection: 4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019)
Issue Date: 2019
Date of publication: 18.06.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI