## MEMBERS

### Program Members

Figure 1: Efficient computation using graph c rewriting by sharing terms

Even before computers were born, the graph structure has been an important subject of research and application as it is a basic tool to intuitively describe a complex situation. However, after the introduction of computers, the graph structure has been used not only as an internal expression within a computer program (data structure), but also as a newly devised computational system to execute a computation by rewriting a 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 structure(graph theory). Moreover, a viewpoint is needed to construct an algorithm based on the assumption that a computer’s hardware has a certain kind of basic graph rewriting operation rather than an implemented graph rewriting operation on an existing computer. In recent years, there are many research projects 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, whereas graph rewriting enables the improvement of 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.

Figure 2: Branching and converging of a computation, depending on different application locations of conversion rules

Graph rewriting procedures can be computed simultaneously as long as rewriting computation regions do not overlap. Computation algorithms using graph rewriting have been developed for computations, including the length of shortest path in traffic networks, the reliability of networks, and impedance in an electrical circuit. Computations using a rewriting do not always result in 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.

Figure 3: Example of fractal triangles using cellular automaton

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

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

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