ON THE KLEIJN-ROZENBERG K-ADJACENT LANGUAGES

The k-adjacent derivations, which generate the k-adjacent languages, w ere introduced by Kleijn and Rozenberg as an intermediate rewriting pr ocess between context-free rewriting and EOL rewriting. In this paper, we study the generative power of the k-adjacent derivations, in conti nuation of the work of Gonczarowski and Shamir, and Dahlhaus and Gaifm an. We show that these derivations generate languages which satisfy th e following: for all k greater than or equal to 5 the family of the k- adjacent languages contains all EOL languages generated by expanding g rammars (this is a generalization of the result of Dahlhaus and Gaifma n where k = 2); for all k greater than or equal to 3, the family of th e k-adjacent languages contains all ETOL languages generated by expand ing grammars; for k > 2, (k + 1)-adjacency has the same generative pow er as k-adjacency if the productions right-hand sides are large enough ; there are k-adjacent languages, k greater than or equal to 3, which are not ETOL.