Generalized periodicity and primitivity for words |
| |
Authors: | Masami Ito Gerhard Lischke |
| |
Affiliation: | 1. Faculty of Science, Kyoto Sangyo University, Kyoto 603-8555, Japan;2. Institute of Informatics, Faculty of Mathematics and Informatics, Friedrich Schiller University Jena, Ernst-Abbe-Platz 1 – 4, D-07743 Jena, Germany |
| |
Abstract: | 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, n 2 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. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) |
| |
Keywords: | Periodicity of words primitivity of words Marcus contextual languages roots of words and languages computational complexity of languages |
|
|