Recognizing edge replacement graph languages in cubic time. (English) Zbl 0769.68078

Vogler, Walter

Graph grammars and their application to computer science, Proc. 4th Int. Workshop, Bremen/Ger. 1990, Lect. Notes Comput. Sci. 532, 676-687 (1991).

Summary: [For the entire collection see Zbl 0753.00023.]
While in general the recognition problem for (hyper-)edge replacement grammars is NP-complete, there are polynomial algorithms for restricted graph classes. The degree of the corresponding polynomial depends on the size of the right hand sides of the grammar, and this size cannot be restricted without restricting the generative power.
In this paper we show that for the class of cyclically connected graphs the recognition problem for edge replacement grammars can be solved in cubic time, i.e. the degree of the polynomial does not depend on the size of the right hand sides of the grammar. For this result we give a suitable normal form for an edge replacement grammar. The algorithm uses the idea of the Cocke-Kasami-Younger algorithm and depends crucially on an algorithm of Hopcroft and Tarjan, which can be used to determine the form of a derivation tree for the given graph.

MSC:

68Q42	Grammars and rewriting systems
68N20	Theory of compilers and interpreters

Keywords:

triconnected components; cyclically connected graphs; recognition problem for edge replacement grammars

Citations:

Zbl 0753.00023