The graph structure has been a subject of research and application even before computers were created, as it is a basic tool to intuitively describe a complex situation. However, since the introduction of computers, the graph structure has been used not only for internal expression within a computer program (data structure), but also as a newly devised computational system to execute a computation by rewriting the graph itself. These advances have made conducting research on the property changes of a graph due to an operation on the graph (graph rewriting theory) particularly important, in addition to the conventional research on static graph structures (graph theory). Moreover, a viewpoint is needed for constructing an algorithm based on the assumption that a computer’s hardware has a certain kind of basic graph rewriting operation, rather than graph rewriting operation being implemented on an existing computer. There have been many research projects recently to devise and design computers within the framework of natural computation, such as molecular computation and quantum computation, which necessitate the fundamental theory of computation using graph rewriting theory.

Formula translation with a computer is executed by expressing a formula using a tree structure and by altering part of the tree corresponding to a pattern to calculate or transform the formula. Graph rewriting improves the computation efficiency by expressing a formula with a graph structure that shares the same terms within the formula (Fig. 1). In this process, a pattern matching algorithm for the graph structure and a graph formalization that does not change the meaning of a formula are important.

Graph rewriting procedures can be computed simultaneously as long as the rewriting computation regions do not overlap. Computation algorithms using graph rewriting have been developed for computations such as the shortest path length in traffic networks, the reliability of networks, and impedance in an electrical circuit. Computations using a rewriting do not always produce the same computation result because computation processes branch out due to application locations and the application order of rewriting (Fig. 2). For this reason, it is important to theoretically confirm that these branches are always confluent or to construct rewriting rules to derive the same computation result.

Computation by transforming a graph, which is a connection of points on a straight line, is closely related to computation using a cellular automaton, which is applied to modeling physical phenomena (Fig. 3). A molecular computation, which uses a DNA strand as in a gene, is considered a possible device to directly achieve a computation mechanism using a cellular automaton. Theories of computability for a graph rewriting system and cellular automaton, computational universality, and computational equivalence can be used to evaluate the effectiveness of computer performance.

Formulating a simultaneous parallel computation of graph conversion and demonstrating computation convergence, algebraic methods, including discrete mathematics, relational algebra theory using binary relations, and category theory are necessary. Furthermore, evaluation of computability requires automata and language theory, computation theory, and mathematical logic theory. Theoretical computer science is not only the theory of data structures and algorithms to be used with current computers, but also the theory of logic and computation to design and devise computers for future computer architecture.

Our research group is conducting research in mathematics and theoretical computer science to revolutionize technologies utilizing computers, which are the foundation of our modern information-based society, as well as to develop novel computation mechanisms.