A Computational Model for Generic Graph Functions

The generic graph machine, a Turing machine-like computation model for generic graph functions, is introduced. A configuration of this machine consists of a number of machine instances that each are in a state and point to two nodes of a graph. During the execution of a step, the machine instances perform in parallel a local transformation on the graph and are each replaced by a number of other machine instances. It is proved that the generic graph machines express a large and natural class of generic graph functions. 1 Introduction If we represent a database as a (labeled) graph, database manipulations can be modeled as partial functions mapping graphs to graphs [3]. We call such functions graph functions. However, not all graph functions can be interpreted as data manipulations. Indeed, they should satisfy at least the following two requirements. First, the function should be computable in the classical sense, i.e., there must be a Turing machine which, when presented an encoding o..