|Abstract of Paper|
Automatic Graphs and Graph $D0L$-Systems
by Olivier Ly
We deal with the concept of end, which is a classical mean to understand the behavior of a graph at infinity. In this respect, we show that the problem of deciding whether an infinite automatic graph has more than one end is recursively undecidable. The proof involves the analysis of some global topological properties of the configuration graph of a self-stabilizing Turing machine. Note that this question has been recently proved to be decidable for the sub-class consisting of the automatic graphs which are the Cayley graphs of word-hyperbolic groups. This result is applied to show the undecidability of connectivity of all the finite graphs produced by iterating a graph $D0L$-system. This comes from the fact that any $D0L$-sequence of finite graphs is encoded by an automatic structure in the sense that it is the sequence of the spheres of an automatic graph; and converse is true for a large class of automatic graphs. We also prove that the graph $D0L$-systems with which we deal can emulate hyperedge replacement systems for which the above connectivity problem is decidable; this result thus contributes in clearing up the decidability boundary of the connectivity question considered here.