A String-Rewriting Characterization of Muller and Schupp’s Context-Free Graphs

This paper introduces Thue specifications, an approach for string-rewriting description of infinite graphs. It is shown that strongly reduction-bounded and unitary reduction-bounded rational Thue specifications have the same expressive power and both characterize the context-free graphs of Muller and Schupp. The problem of strong reduction-boundedness for rational Thue specifications is shown to be undecidable but the class of unitary reduction-bounded rational Thue specifications, that is a proper subclass of strongly reduction-bounded rational Thue specifications, is shown to be recursive.