Caucal, Didier On the regular structure of prefix rewriting. (English) Zbl 0786.68047 CAAP’90, Proc. 15th Colloq., Copenhagen/Denmark 1990, Lect. Notes Comput. Sci. 431, 87-102 (1990). [For the entire collection see Zbl 0745.00027.]In a seminal paper, Muller and Schupp have proved that every pushdown transition graph has a regular structure, which can be generated via a deterministic graph grammar. We will give an effective proof of this result, by writing a procedure which produces the graph grammar (section 3). Conversely, we will also show that any rooted graph with finite degree, generated by a deterministic graph grammar, is isomorphis to a prefix transition graph, and we moreover give a procedure which produces the corresponding rewriting system (also in section 3). At last, we establish effectively the characterisation of D. E. Muller and P. E. Schupp [Theor. Comput. Sci. 37, 51-75 (1985; Zbl 0605.03005)]. As a corollary, we can decide that two prefix transition graphs are isomorphic with respect to some given vertices. Cited in 6 Documents MSC: 68Q42 Grammars and rewriting systems Keywords:rewriting system; prefix rewriting; regular language; pushdown transition graph; deterministic graph grammar; graph grammar Citations:Zbl 0745.00027; Zbl 0605.03005 PDFBibTeX XMLCite \textit{D. Caucal}, Lect. Notes Comput. Sci. 431, 87--102 (1990; Zbl 0786.68047)