Tracelets and Tracelet Analysis Of Compositional Rewriting Systems

Nicolas Behr
(Université de Paris, IRIF, CNRS, F-75013 Paris, France)

Taking advantage of a recently discovered associativity property of rule compositions, we extend the classical concurrency theory for rewriting systems over adhesive categories. We introduce the notion of tracelets, which are defined as minimal derivation traces that universally encode sequential compositions of rewriting rules. Tracelets are compositional, capture the causality of equivalence classes of traditional derivation traces, and intrinsically suggest a clean mathematical framework for the definition of various notions of abstractions of traces. We illustrate these features by introducing a first prototype for a framework of tracelet analysis, which as a key application permits to formulate a first-of-its-kind algorithm for the static generation of minimal derivation traces with prescribed terminal events.

In John Baez and Bob Coecke: Proceedings Applied Category Theory 2019 (ACT 2019), University of Oxford, UK, 15-19 July 2019, Electronic Proceedings in Theoretical Computer Science 323, pp. 44–71.
Published: 15th September 2020.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: