EXPANDING GRAPH RELABELING SYSTEMS HAVE THE POWER OF RECURSIVE ENUMERABILITY

Article type: Research Article

Authors: Sopena, Eric

Affiliations: LaBRI, Université Bordeaux 1. 351. Cours de la Libération. F-33405 Talence. France

Abstract: Graph relabeling systems (GRS's) have been introduced as a suitable tool for coding and proving sequential or distributed algorithms on graphs or networks. These systems do not change the underlying structure of the graph on which they work, but only the labeling of its components (edges or vertices). Each relabeling step is fully determined by the knowledge of a fixed size subgraph, the relabeled occurrence. We introduce an extension of that model, the so-called expanding graph relabeling systems (e-GRS's), which allows the generation of sets of graphs by means of component relabeling. We study the generating power of these systems and prove that they enable us to generate any recursively enumerable set of graphs. We first show how the “from left to right” natural orientation of a string-graph, that is a graph representation of a string, can be translated by means of vertex labels in such a way that any local transformation of the string can be simulated by a local relabeling of the string-graph vertices. Using this translation, we show that any phrase-structure string grammar can be simulated by an e-GRS. Finally, we provide a way of encoding graphs as strings and an e-GRS, called the decoder, which can convert any string representation of the encoding of a graph into the graph itself.

DOI: 10.3233/FI-1996-27101

Journal: Fundamenta Informaticae, vol. 27, no. 1, pp. 1-25, 1996