Generic strategies for chemical space exploration

Undirected labeled graphs and graph rewriting are natural models of chemical compounds and chemical reactions. This provides a basis for exploring spaces of molecules and computing reaction networks implicitly defined by graph grammars. Molecule graphs are connected, meaning that rewriting steps in general are many-to-many graph transformations. Chemical grammars are typically subject to combinatorial explosion, however, making it often infeasible to compute the underlying network by direct breadth-first expansion. To alleviate this problem, we introduce here partial applications of rules as a basis for the efficient implementation of strategies that are not only well suited for exploration of chemistries defined by graph grammars, but that are also applicable in a general graph rewriting context as well. As showcases, we explore a complex chemistry based on the Diels-Alder reaction to explore specific subspaces of the molecular space. As a non-chemical application we use the framework of exploration strategies to model an abstract graph rewriting problem to construct high-level transformations that cannot be directly represented the Double-Pushout formalism starting from simple DPO transformation rules.