On derivation preservation (Q1058859)

A homomorphism h between the production sets of two context-free grammars \(G_ 1\) and \(G_ 2\) is said to ''preserve derivations'' if it maps derivations to derivations and terminal derivations to terminal derivations. The concept of derivation preservation is common to some of the grammatical relations introduced in the literature (cover, undercover, Reynolds cover and SI-cover). The paper studies the properties of a nonterminal relation induced a by derivation preserving homomorphism h. Finally, it is shown that it is decidable whether or not homomorphism h preserves derivations in a system \((G_ 1,G_ 2,h)\).