In the last years there has been a growing interest towards categorical models for term rewriting systems (TRSs). In our opinion, very interesting are those associating to each TRS a cat-enriched structure: a category whose hom-sets are categories. Interpreting rewriting steps as morphisms in hom-categories, these models provide rewriting systems with a concurrent semantics in a clean algebraic way. In this paper we provide a unified presentation of two models recently proposed in literature by José Meseguer and John Stell, respectively, pursuing a critical analysis of both of them. More precisely, we show why they are to a certain extent unsatisfactory in providing a concurrent semantics for rewriting systems. It turns out that the derivation space of Meseguer's Rewriting Logic associated with each term (i.e., the set of coinitial computations) fails in general to form a prime algebraic domain: a condition that is generally considered as expressing a directly implementable model of concurrency for distributed systems. On the contrary, the resulting derivation space in Stell's model is actually a prime algebraic domain, but too few computations are identified: only disjoint concurrency can be expressed, limiting the degree of parallelism described by the model.

Relating Two Categorial Models of Term Rewriting

CORRADINI, ANDREA;GADDUCCI, FABIO;MONTANARI, UGO GIOVANNI ERASMO
1995

Abstract

In the last years there has been a growing interest towards categorical models for term rewriting systems (TRSs). In our opinion, very interesting are those associating to each TRS a cat-enriched structure: a category whose hom-sets are categories. Interpreting rewriting steps as morphisms in hom-categories, these models provide rewriting systems with a concurrent semantics in a clean algebraic way. In this paper we provide a unified presentation of two models recently proposed in literature by José Meseguer and John Stell, respectively, pursuing a critical analysis of both of them. More precisely, we show why they are to a certain extent unsatisfactory in providing a concurrent semantics for rewriting systems. It turns out that the derivation space of Meseguer's Rewriting Logic associated with each term (i.e., the set of coinitial computations) fails in general to form a prime algebraic domain: a condition that is generally considered as expressing a directly implementable model of concurrency for distributed systems. On the contrary, the resulting derivation space in Stell's model is actually a prime algebraic domain, but too few computations are identified: only disjoint concurrency can be expressed, limiting the degree of parallelism described by the model.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/182427
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
  • ???jsp.display-item.citation.isi??? ND
social impact