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

Lautemann, Clemens

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.

MSC:

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

Keywords:

context-free graph languages; boundary node-label controlled grammars; hyperedge replacement grammars; graph grammar; context-free string languages; complexity

Citations:

Zbl 0639.00042