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

Khasidashvili, Zurab and Glauert, John 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
UEA Research Groups:	Faculty of Science > Research Groups > Interactive Graphics and Audio Faculty of Science > Research Groups > Computer Graphics (former - to 2018)
Depositing User:	Vishal Gautam
Date Deposited:	13 Jun 2011 13:13
Last Modified:	16 Jun 2023 23:44
URI:	https://ueaeprints.uea.ac.uk/id/eprint/22844
DOI:	10.1016/S0304-3975(01)00235-3

Actions (login required)

View Item