Relating conflict-free stable transition and event models via redex families

Khasidashvili, Z. and Glauert, J. R. W. (2002) Relating conflict-free stable transition and event models via redex families. Theoretical Computer Science, 286 (1). pp. 65-95. ISSN 0304-3975

Full text not available from this repository. (Request a copy)

Abstract

We describe an event-style (or poset) semantics for conflict-free rewrite systems, including term and graph rewriting (possibly with bound variables), the ?-calculus, and other stable transition systems with a residual relation. Our interpretation is based on considering redex-families as events. It treats permutation-equivalent reductions as representing the same concurrent computation. Due to erasure of redexes, event structures are inadequate for such an interpretation. We therefore extend the prime event structure model in two different but equivalent ways: by axiomatizing permutation-equivalence on finite configurations, and by axiomatizing the erasure of events, for the conflict-free case, and show that these extended models are equivalent to stable transition models with axiomatized residual and family relations. We then construct finitary prime algebraic domains from the set of configurations in these extended models by defining orderings relative to stable sets of ‘results’. All useful sets of results for which the normalization (by neededness) theorem can be proved are stable.

Item Type: Article
Faculty \ School: Faculty of Science > School of Computing Sciences
Related URLs:
Depositing User: Vishal Gautam
Date Deposited: 13 Jun 2011 14:13
Last Modified: 19 Sep 2018 13:31
URI: https://ueaeprints.uea.ac.uk/id/eprint/22844
DOI: 10.1016/S0304-3975(01)00235-3

Actions (login required)

View Item