Abstract
We propose an algebraic approach to stochastic graphrewriting which extends the classical construction of the HeisenbergWeyl algebra and its canonical representation on the Fock space. Rules are seen as particular elements of an algebra of “diagrams”: the diagram algebra D. Diagrams can be thought of as formal computational traces represented in partial time. They can be evaluated to normal diagrams (each corresponding to a rule) and generate an associative unital
noncommutative algebra of rules: the rule algebra R. Evaluation becomes a morphism of unital associative algebras which maps general diagrams in D to normal ones in R. In this algebraic reformulation, usual distinctions between graph observables (realvalued maps on the set of graphs defined by counting subgraphs) and rules disappear. Instead, natural algebraic substructures ofR arise: formal observables are seen as rules with equal left and right hand sides and form a commutative subalgebra, the ones counting subgraphs forming a subsubalgebra of identity rules. Actual graphrewriting is recovered as a canonical representation of the rule algebra as linear operators over the vector space generated by (isomorphism classes of) finite graphs. The construction of the representation is in close analogy with and subsumes the classical (multitype bosonic) Fock space representation of the HeisenbergWeyl algebra. This shift of point of view, away from its canonical representation to the rule algebra itself, has unexpected consequences. We find that natural variants of the evaluation morphism map give rise to concepts of graph transformations hitherto not considered. These will be described in a separate paper [2]. In this extended abstract we limit ourselves to the simplest concept of doublepushout rewriting (DPO). We establish “jumpclosure”, i.e. that the subspace of representations of formal graph observables is closed under the action of any rule set. It follows that for any rule set, one can derive a formal and selfconsistent Kolmogorov backward equation for (representations of) formal observables.
noncommutative algebra of rules: the rule algebra R. Evaluation becomes a morphism of unital associative algebras which maps general diagrams in D to normal ones in R. In this algebraic reformulation, usual distinctions between graph observables (realvalued maps on the set of graphs defined by counting subgraphs) and rules disappear. Instead, natural algebraic substructures ofR arise: formal observables are seen as rules with equal left and right hand sides and form a commutative subalgebra, the ones counting subgraphs forming a subsubalgebra of identity rules. Actual graphrewriting is recovered as a canonical representation of the rule algebra as linear operators over the vector space generated by (isomorphism classes of) finite graphs. The construction of the representation is in close analogy with and subsumes the classical (multitype bosonic) Fock space representation of the HeisenbergWeyl algebra. This shift of point of view, away from its canonical representation to the rule algebra itself, has unexpected consequences. We find that natural variants of the evaluation morphism map give rise to concepts of graph transformations hitherto not considered. These will be described in a separate paper [2]. In this extended abstract we limit ourselves to the simplest concept of doublepushout rewriting (DPO). We establish “jumpclosure”, i.e. that the subspace of representations of formal graph observables is closed under the action of any rule set. It follows that for any rule set, one can derive a formal and selfconsistent Kolmogorov backward equation for (representations of) formal observables.
Original language  English 

Title of host publication  LICS '16 Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science 
Publisher  ACM 
Pages  4655 
Number of pages  10 
Volume  New York, USA 
ISBN (Print)  9781450343916 
DOIs  
Publication status  Published  5 Jul 2016 
Event  31st Annual ACM/IEEE Symposium on Logic in Computer Science  New York City, United States Duration: 5 Jul 2016 → 8 Jul 2016 http://lics.siglog.org/lics16/ 
Conference
Conference  31st Annual ACM/IEEE Symposium on Logic in Computer Science 

Abbreviated title  LICS 2016 
Country  United States 
City  New York City 
Period  5/07/16 → 8/07/16 
Internet address 
Fingerprint Dive into the research topics of 'Stochastic mechanics of graph rewriting'. Together they form a unique fingerprint.
Profiles

Vincent Danos
 School of Informatics  Chair of Computational Systems Biology
 Laboratory for Foundations of Computer Science
 Foundations of Computation
 SynthSys
Person: Academic: Research Active