×

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.

MSC:

68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite