Loading...
Please wait, while we are loading the content...
Similar Documents
From Rewrite Rules to Bisimulation
| Content Provider | Semantic Scholar |
|---|---|
| Author | Sewell, Peter |
| Copyright Year | 2017 |
| Abstract | The dynami s of many al uli an be most learly de ned by a redu tion semanti s. To work with a al ulus, however, an understanding of operational ongruen es is fundamental; these an often be given tra table de nitions or hara terisations using a labelled transition semanti s. This paper onsiders al uli with arbitrary redu tion semanti s of three simple lasses, rstly ground term rewriting, then left-linear term rewriting, and then a lass whi h is essentially the a tion al uli la king substantive name binding. General de nitions of labelled transitions are given in ea h ase, uniformly in the set of rewrite rules, and without requiring the pres ription of additional notions of observation. They give rise to bisimulation ongruen es. As a test of the theory it is shown that bisimulation for a fragment of CCS is re overed. The transitions generated for a fragment of the Ambient Cal ulus of Cardelli and Gordon, and for SKI ombinators, are also dis ussed brie y. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cl.cam.ac.uk/~pes20/labels-tcs-final.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
