Premium
Generalized periodicity and primitivity for words
Author(s) -
Ito Masami,
Lischke Gerhard
Publication year - 2007
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.200610030
Subject(s) - mathematics , turing machine , turing , combinatorics , linguistics , discrete mathematics , computer science , algorithm , philosophy , computation , programming language
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)