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

C. Martin-Vide, A. Mateescu, J. Miquel-Verg~es, Ch. Paun

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.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.