Efficient algorithms on context-free graph languages. (English) Zbl 0649.68075

Automata, languages and programming, Proc. 15th Int. Colloq., Tampere/Finn. 1988, Lect. Notes Comput. Sci. 317, 362-378 (1988).
Summary: [For the entire collection see Zbl 0639.00042.]
A number of different graph grammar types have been called “context- free” in the literature. We consider two recent such formalisms, boundary node-label controlled (BNLC) and hyperedge replacement (HR) grammars, from a complexity-theoretical point of view. It is shown that all HR languages, the members of which satisfy a certain separability restriction, are contained in LOGCFL, the class of sets which are log- space reducible to context-free (string) languages. In particular, this implies the existence of efficient sequential as well as parallel recognition algorithms for these languages. Since HR grammars can simulate a large class of BNLC grammars, the same holds for an according class of BNLC languages. Thus, in a sense, a large class of BNLC and HR languages are “close” to context-free string languages.
We then use these results for investigating the complexity of some graph- theoretical problems restricted to HR languages. It is shown that on HR languages which satisfy the abovementioned constraints, a number of problems (some of which are NP-complete in the general case) have polynomial-time sequential and very fast and feasible parallel solutions.


68Q45 Formal languages and automata
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity


Zbl 0639.00042