Discrimination Nets: Improvement and Extension to Bang Graphs
Date:
MSc Dissertation.
String graphs constitute a graphical language to represent many types of processes and phenomena, including quantum phenomena. Because of their discrete nature, string graphs can be easily processed by a computer. A well-known family of filtering techniques used to speed up the process of graph matching are discrimination nets. Discrimination nets were applied to string graphs by Douglas in 2010. In this dissertation we first propose an improved algorithm for discrimination nets when working with string graphs; then we define an extension of the algorithm for discrimination nets when dealing with !-graphs. We give a proof of the correctness of our algorithms and we offer an implementation of these algorithms within the context of Quantomatic. Finally we present a set of results obtained by running simulations of our algorithms with randomly generated string graphs and !-graphs.