Cyclic Permutations of Letters of Words in Languages over an Alphabet

Abstract

The language classes of the Chomsky hierarchy are known (Ruohonen [6]) to be closed under cyclic permutations on words. For an alphabet Σ, we give a description of the ideals in Σ* that are closed under cyclic permutation of letters in words. Given a regular language L in Σ*, we give two different constructions of automata accepting the language obtained by cyclically permuting the letters of words in L. Finally, we discuss a special family of bounded languages in which, for every regular language L, the full permutation of the letters of the words in L yields a regular language.