Adhesive DPO Parallelism for Monic Matches

Filippo Bonchi, Tobias Heindel

Research output: Contribution to journalArticlepeer-review


This paper presents indispensable technical results of a general theory that will allow to systematically derive from a given reduction system a behavioral congruence that respects concurrency. The theory is developed in the setting of adhesive categories and is based on the work by Ehrig and König on borrowed contexts; the latter are an instance of relative pushouts, which have been proposed by Leifer and Milner. In order to lift the concurrency theory of dpo rewriting to borrowed contexts we will study the special case of dpo rewriting with monic matches in adhesive categories: more specifically we provide a generalized Butterfly Lemma together with a Local Church Rosser and Parallelism theorem.
Original languageEnglish
Pages (from-to)51-61
Number of pages11
JournalElectronic Notes in Theoretical Computer Science
Issue number4
Publication statusPublished - 9 Jul 2007

Fingerprint Dive into the research topics of 'Adhesive DPO Parallelism for Monic Matches'. Together they form a unique fingerprint.

Cite this