We correct a mistake in the paper “Generalized periodicity and primitivity for words” [4] and justify the existence of regular languages all of whose roots are not even context-sensitive.

Starting from six kinds of periodicity of words we define six sets of words which are primitive in different senses and we investigate their relationships. We show that only three of the sets are external Marcus contextual languages with choice but none of them is an external contextual language without choice or an internal contextual language. For the time complexity of deciding any of our sets by one-tape Turing machines, n2 is a lower bound and this is optimal in two (...) cases. The notions of roots and degrees of words and languages, which are strongly connected to periodicity and primitivity, are also considered, and we show that there can be an arbitrarily large gap between the complexity of a language and that of its roots. (shrink)

Punctured languages are languages whose words are partial words in the sense that the letters at some positions are unknown. We investigate to which extent restoration of punctured languages is possible if the number of unknown positions or the proportion of unknown positions per word, respectively, is bounded, and we study their relationships for different boundings. The considered restoration classes coincide with similarity classes according to some kind of similarity for languages. Thus all results we can also formulate in the (...) language of similarity. We show some hierarchies of similarity classes for each class from the Chomsky hierarchy and prove the existence of linear languages which are not δ -similar to any regular language for any δ < ½. For δ ≥ ½ this is unknown but it could only be possible in the case of non-slender linear languages. (shrink)

The square of a language L is the set of all words pp where p ∈ L. The square of a regular language may be regular too or context-free or none of both. We give characterizations for each of these cases and show that it is decidable whether a regular language has one of these properties.

We consider the relationship between the computational complexity classes NP and EL . Taking into account the inclusion or incomparability of these classes, the existence or nonexistence of immune sets in their differences, and the existence or nonexistence of sparse sets in the differences, there are exactly 24 different cases for their relationship. We show that 16 cases are impossible in the real nonrelativized world as well as in any relativized world. Each of the remaining 8 cases is realizable in (...) appropriate relativized worlds. Further we examine which of the 8 cases is most probably for a random oracle. (shrink)