I am currently completing a dissertation in which I derive a general pattern matching algorithm using Grothendieck topologies. For the related work section, I am looking for other applications in computer science of Grothendieck topologies or sheaf theory. I already have the following references: Michel Eytan's PhD thesis (which applies Grothendieck topologies to grammars), and Monteiro and Pereira's paper on modeling concurrency using sheaves. If you know of any other applications, could you please send me a message? The abstract of my dissertation is enclosed. The dissertation will be ready for distribution in early April. If you would like a copy, please let me know. - srinivas PATTERN MATCHING: A SHEAF-THEORETIC APPROACH Yellamraju V. Srinivas PhD Dissertation (forthcoming March 1991) University of California, Irvine SUMMARY: A general theory of pattern matching is presented by adopting an extensional, geometric view of patterns. The extension of the matching relation consists of the occurrences of all possible patterns in a particular target. The geometry of the pattern describes the structure of the pattern and the spatial relationships among parts of the pattern. The extension and the geometry, when combined, produce a structure called a sheaf. Sheaf theory is a well developed branch of mathematics which studies the global consequences of locally defined properties. For pattern matching, an occurrence of a pattern, a global property of the pattern, is obtained by gluing together occurrences of parts of the pattern, which are locally defined properties. A sheaf-theoretic view of pattern matching provides a uniform treatment of pattern matching on any kind of data structure---strings, trees, graphs, hypergraphs, and so on. Such a parametric description is achieved by using the language of category theory, a highly abstract description of commonly occurring structures and relationships in mathematics. A generalized version of the Knuth-Morris-Pratt pattern matching algorithm is derived by gradually converting the extensional description of pattern matching as a sheaf into an intensional description. The algorithm results from a synergy of four very general program synthesis/transformation techniques: (1) Divide and conquer: exploit the sheaf condition; assemble a full match by gluing together partial matches; (2) Finite differencing: collect and update partial matches incrementally while traversing the target; (3) Backtracking: instead of saving all partial matches, save just one; when this partial match cannot be extended, fail back to another; (4) Partial evaluation: precompute pattern-based (and therefore constant) computations into an automaton. The derivation is carried out in a general framework using Grothendieck topologies. By appropriately instantiating the underlying data structures and topologies, the same scheme results in matching algorithms for patterns with variables and with multiple patterns. Slight variations of the derivation result in Earley's algorithm for context-free parsing, LR parsing, and Waltz filtering, a relaxation algorithm for providing 3-D interpretations to 2-D images. Other applications of a geometric view of patterns are briefly considered: rewrites, parallel algorithms, induction and computability. ======== Y. V. Srinivas E-mail: srinivas@ics.uci.edu Information and Computer Science University of California Irvine, CA 92717, USA