6 juin 2016
Luidnel Maignan (LACL)Most of graph rewritting models are “asynchronous”. When many parts of a graph should be rewritten, a rewritting order has to be chosen. They are also often “non-deterministic”. Rewritting one part may prevent another overlapping part to be rewritten, making the different orders non-equivalent. Determinism is achieved only when there is a kind of mutual exlusion. In the spirit of cellular automata, we design a formal framework to speak about graph rewrittings where all the graph is modified synchronously and determinism is achieved by a notion of “mutual agreement”. The proposed rewritting process is discussed and finally formalized efficiently using the categorical toolkit. This is a joint work with Antoine Spicher.