External Contextual and Conditional Languages

. We investigate three dierent aspects of external contextual languages, focusing mainly on linear selector sets: (1) comparison with conditional languages regarding their descriptive capacity (2) as well as their computational complexity and (3) inductive inference of external contextual languages with various selector set families. 1 Introduction External contextual grammars were dened by Marcus [24] in 1969 in order to model basic phenomena in descriptive linguistics. The generative process in a contextual grammar is based on the linguistic operation of inserting a word into a given context. Independently, only one year later, Navratil [25] presented conditional grammars|context-free grammars with regular conditions|in order to model more natural phenomena using context-independent derivation rules. There, a production ! is applicable to a sentential form xy if the sentential form belongs to the condition set of ! . Since the introduction of both concepts, many for..