On the structure of linear apex NLC graph grammars

AbstractIt is known that linear apex NLC (Lin-A-NLC) grammars can generate NP-complete graph languages. The present paper examines the source of this expressive power by analyzing complexity and decidability of the so-called k-connecting Lin-A-NLC (k-Lin-A-NLC) grammars in which the right-hand side of each production contains at most k nodes that can be connected to outside nodes. The number of connecting nodes is indeed one source of the expressive power of graph grammars in that k-Lin-A-NLC ⊊(k+1)-Lin-A-NLC for every k≥0. There exists a 2-Lin-A-NLC language which is NP-complete but every 1-Lin-A-NLC language is in NLOG. The equivalence problem is undecidable for 1-Lin-A-NLC languages but is decidable for 0-Lin-A-NLC languages (even when one of two input languages is an arbitrary B-NLC language)