<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

On probabilistic term rewriting

descriptionPublicationkeyboard_double_arrow_right Article , Part of book or chapter of book , Preprint , Conference object 01 Jan 2018Embargo end date: 01 Jan 2018 France, Italy English Publisher:Elsevier BVJournal:Science of Computer Programming, volume 185, page 102,338 (issn: 0167-6423,

Authors: Akihisa Yamada; Martin Avanzini; Ugo Dal Lago; Ugo Dal Lago;

doi: 10.1016/j.scico.2019.102338 , 10.1007/978-3-319-90686-7_9 , 10.48550/arxiv.1802.09774

arXiv: http://arxiv.org/abs/1802.09774

handle: 11585/664492 , 11585/798437

On probabilistic term rewriting

- Summary
- Subjects
- Metrics

Abstract

We study the termination problem for probabilistic term rewrite systems. We prove that the interpretation method is sound and complete for a strengthening of positive almost sure termination, when abstract reduction systems and term rewrite systems are considered. Two instances of the interpretation method - polynomial and matrix interpretations - are analyzed and shown to capture interesting and nontrivial examples when automated. We capture probabilistic computation in a novel way by way of multidistribution reduction sequences, this way accounting for both the nondeterminism in the choice of the redex and the probabilism intrinsic in firing each rule.

Technical Report of our FLOPS'18 paper

Countries

France, Italy

Related Organizations

Alma Mater Studiorum University of Bologna
Italy
GNA University
India
INRIA Sophia Antipolis (Valbonne)
France
INRAE Sophia Antipolis (Biot)
France
French Institute for Research in Computer Science and Automation
France

View all View all

Keywords

Computer Science - Symbolic Computation, FOS: Computer and information sciences, Almost sure termination; Interpretation method; Probabilistic abstract reduction systems; Probabilistic term rewriting, term rewriting systems, termination, probabilistic computation, [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], Symbolic Computation (cs.SC), [INFO.INFO-PL] Computer Science [cs]/Programming Languages [cs.PL], Almost sure termination, Probabilistic abstract reduction systems, Interpretation method, Probabilistic term rewriting, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC]

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	29
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%