License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2008.1764
URN: urn:nbn:de:0030-drops-17643
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1764/
Go to the corresponding LIPIcs Volume Portal

Rodriguez-Hortala, Juan

A Hierarchy of Semantics for Non-deterministic Term Rewriting Systems

pdf-format:
08004.Rodriguez_Hortala.1764.pdf (0.4 MB)

Abstract

Formalisms involving some degree of nondeterminism are frequent in computer science. In particular, various programming or specification languages are based on term rewriting systems where confluence is not required. In this paper we examine three concrete possible semantics for non-determinism that can be assigned to those programs. Two of them --call-time choice and run-time choice-- are quite well-known, while the third one --plural semantics-- is investigated for the first time in the context of term rewriting based programming languages. We investigate some basic intrinsic properties of the semantics and establish some relationships between them: we show that the three semantics form a hierarchy in the sense of set inclusion, and we prove that call-time choice and plural semantics enjoy a remarkable compositionality property that fails for run-time choice; finally, we show how to express plural semantics within run-time choice by means of a program transformation, for which we prove its adequacy.

BibTeX - Entry

@InProceedings{rodriguezhortala:LIPIcs:2008:1764,
  author =	{Juan Rodriguez-Hortala},
  title =	{{A Hierarchy of Semantics for Non-deterministic Term Rewriting Systems}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{328--339},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Ramesh Hariharan and Madhavan Mukund and V Vinay},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1764},
  URN =		{urn:nbn:de:0030-drops-17643},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1764},
  annote =	{Keywords: Functional-logic programming, term rewriting systems, constructor-based rewriting logic, non-determinism, call-time choice semantics, run-time choice }
}

Keywords: Functional-logic programming, term rewriting systems, constructor-based rewriting logic, non-determinism, call-time choice semantics, run-time choice
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Issue Date: 2008
Date of publication: 05.12.2008

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