Internal Contextual Grammars: Minimal, Maximal, and Scattered Use of Selectors

Proceedings of the Fourth Bar-Ilan Symposium on Foundations of Artificial Intelligence

Volume

Proceedings of the Fourth Bar-Ilan Symposium on Foundations of Artificial Intelligence

Contents

We consider internal contextual grammars (with finite and with regular selection sets) with the derivation restricted in the following way: when a word is used as a selector, then no subword/superword of it can be used as a selector. This can be considered both locally (with respect to the choosen selec-tion set) or globally (with respect to all selection sets). The generative capacity of such grammars is investigated (comparing each other the above mentioned variants and with the class of unrestricted internal contextual grammars). Finally, grammars with selectors checked as scattered subwords of the derived words are considered.