On the regular structure of prefix rewriting (Q685354)

A labelled word rewriting system \(R\) on an alphabet \(X\) and a set \(L\) of labels is a finite set of labelled transitions \(u@>a>>v\) where \(a\) is a label and \(u\) and \(v\) are words over \(X\). The prefix transition graph of \(R\) is the infinite set of labelled transitions \(uw@>a>>vw\) where \(u@>a>>v\) is a rule of \(R\) and \(w\) is a word over \(X\). We show that any prefix transition graph is effectively a regular graph of finite degree: it is produced from a finite graph by iterating the addition of a finite family of finite graphs. It turns out that the rational restrictions of the prefix transition graphs are exactly the regular graphs of finite degree. Furthermore we show that the prefix transition graphs and the regular graphs of finite degree have the same connected components and the same accessible subgraphs. Finally we establish that the prefix transition graphs corresponds to the transition graphs of pushdown automata. All constructions are effective.