Sesqui-Pushout Rewriting: Concurrency, Associativity and Rule Algebra Framework

Nicolas Behr
(Université de Paris, IRIF, CNRS)

Sesqui-pushout (SqPO) rewriting is a variant of transformations of graph-like and other types of structures that fit into the framework of adhesive categories where deletion in unknown context may be implemented. We provide the first account of a concurrency theorem for this important type of rewriting, and we demonstrate the additional mathematical property of a form of associativity for these theories. Associativity may then be exploited to construct so-called rule algebras (of SqPO type), based upon which in particular a universal framework of continuous-time Markov chains for stochastic SqPO rewriting systems may be realized.

In Rachid Echahed and Detlef Plump: Proceedings Tenth International Workshop on Graph Computation Models (GCM 2019), Eindhoven, The Netherlands, 17th July 2019, Electronic Proceedings in Theoretical Computer Science 309, pp. 23–52.
Published: 20th December 2019.

ArXived at: http://dx.doi.org/10.4204/EPTCS.309.2 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org