EOL and ETOL Systems with Control Devices

Abstract

The effects of 1) regular control, 2) appearance checking, and 3) minimal table interpretation on extended (partial table) OL systems with respect to the generative capacity are studied. It is proved that the effect of 3) is strictly stronger that the effects of 1) and 2), and equal to the effect of the combination of l) and 2). This implies among other things that appearance checking increases the generative capacity of the systems with regular control - the corresponding problem for ordinary grammars being still open. Finally, the notions of matrix and vector control are introduced and some results on the effects of these mechanisms are proved. These results turn out to be very much different from the corresponding well-known results for context free grammars-differences, of course, due to the different natures of CF-grammars and EOL-systems.