Generalized periodicity and primitivity for words
Generalized periodicity and primitivity for words
复制标题
DOI：
10.1002/malq.200610030
复制
发表时间：
2007-01
影响因子：
0.3
通讯作者：
Masami Ito;G. Lischke
中科院分区：
文献类型：
--
作者：
Masami Ito;G. Lischke
从词的六种周期性出发，定义了六组不同意义上的原始词，并考察了它们之间的关系。我们发现，只有三个集是外部马库斯上下文语言的选择，但没有一个是没有选择的外部上下文语言或内部上下文语言。对于单带图灵机决定任何集合的时间复杂度，n 2是一个下界，在两种情况下这是最优的。根的概念和程度的话和语言，这是强烈连接到周期性和连续性，也被认为是，我们表明，可以有一个任意大的差距之间的复杂性的语言和它的根源。（© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA，魏因海姆）
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)