Dr. Nicolas Behr, IRIF, Université Paris Diderot, France

Rewriting theory for the social and life sciences

Abstract:
Somewhat surprisingly, despite the widespread use of models based upon transformations of graph-like objects in the applied sciences (chemical reaction systems, network models, random graph ensembles, tissue models, agent-based models, ...), the underlying theory and mathematics of so-called rewriting over adhesive categories appears to be relatively little known. In this talk, I will give a concise introduction to modern rewriting theory, and I will present two novel mathematical extensions of this framework: so-called rule algebras and tracelets for rewriting theories. Rule algebras permit to formulate a universal framework of continuous-time Markov chains arising from random transformation systems of graph-like structures, yielding a new tool-set for analyzing these systems, including in particular so-called combinatorial conversion (which permits to derive ODEs for the evolution of the statistical moments of pattern-counting observables). Tracelets on the other hand provide a mathematical formalism to extract high-level causal information from specifications of rewriting systems in terms of transformation rules and their base rates, sometimes referred to as "synthesis of explanations" (as opposed to the more standard approach of extracting statistical information from simulations). Originally developed as a precise mathematical implementation of the notion of pathways in biochemical reaction systems, this methodology aims to find high-level causal structures in sequences of rule compositions that permit to understand the dynamical behaviors of the typically highly complex random transformation system at hand. I will illustrate these novel concepts with application examples (such as a voter model of opinion formation) and provide some perspectives for high-performance software implementations of both the rule algebra and tracelet methodologies.