Abstract of Paper

Automatic Graphs and Graph $D0L$-Systems
by Olivier Ly

Abstract:

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.