String diagrams provide a convenient graphical framework which may be used for equational reasoning about morphisms of monoidal categories. However, unlike term rewriting, which is the standard way of reasoning about the morphisms of monoidal categories, rewriting string diagrams results in shorter equational proofs, because the string diagrammatic representation allows us to formally establish equalities modulo any rewrite steps which follow from the monoidal structure. Manipulating string diagrams by hand is a time-consuming and error-prone process, especially for large string diagrams. This can be ameliorated by using software proof assistants, such as Quantomatic. However, reasoning about concrete string diagrams may be limiting and in some scenarios it is necessary to reason about entire (infinite) families of string diagrams. When doing so, we face the same problems as for manipulating concrete string diagrams, but in addition, we risk making further mistakes if we are not precise enough about the way we represent (infinite) families of string diagrams. The primary goal of this thesis is to design a mathematical framework for equational reasoning about infinite families of string diagrams which is amenable to computer automation. We will be working with context-free families of string diagrams and we will represent them using context-free graph grammars. We will model equations between infinite families of diagrams using rewrite rules between context-free grammars. Our framework represents equational reasoning about concrete string diagrams and context-free families of string diagrams using double-pushout rewriting on graphs and context-free graph grammars respectively. We will prove that our representation is sound by showing that it respects the concrete semantics of string diagrammatic reasoning and we will show that our framework is appropriate for software implementation by proving important decidability properties.

Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2008. / Includes bibliographical references (p. 120-125). Also available in electronic version.

Thesis (M.Sc.) - Carleton University, 2005. / Includes bibliographical references (p. 61-63). Also available in electronic format on the Internet.

Thesis (MSc)--University of Stellenbosch, 2008. / Bibliography. Also available via the Internet.

Thesis (M. Sc. - Carleton University, 2001. / Includes bibliographical references (p. 138-141). Also available in electronic format on the Internet.

Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2007. / Includes bibliographical references (leaves 106-113). Also available in electronic version.

Thesis (MSc (Mathematical Sciences))--University of Stellenbosch, 2008. / Context-free grammars are well-studied and well-behaved in terms of decidability, but many real-world problems cannot be described with context-free grammars. Grammars with regulated rewriting are grammars with mechanisms to regulate the applications of rules, so that certain derivations are avoided. Thus, with context-free rules and regulated rewriting mechanisms, one can often generate languages that are not context-free. In this thesis we study grammars with regulated rewriting mechanisms. We consider problems in which context-free grammars are insufficient and in which more descriptive grammars are required. We compare bag context grammars with other well-known classes of grammars with regulated rewriting mechanisms. We also discuss the relation between bag context grammars and recognizing devices such as counter automata and Petri net automata. We show that regular bag context grammars can generate any recursively enumerable language. We reformulate the pumping lemma for random permitting context languages with context-free rules, as introduced by Ewert and Van der Walt, by using the concept of a string homomorphism. We conclude the thesis with decidability and complexity properties of grammars with regulated rewriting.

Functional logic languages provide a powerful programming paradigm combining the features of functional languages and logic languages. However, current implementations of functional logic languages are complex, slow, or both. This thesis presents a scheme, called the Basic Scheme, for compiling and executing functional logic languages based on non-deterministic graph rewriting. This thesis also describes the implementation and optimization of a prototype of the Basic Scheme. The prototype is simple and performs well compared to other current implementations.