Words and forbidden factors
Words and forbidden factors
复制标题
DOI：
10.1016/s0304-3975(00)00436-9
复制
发表时间：
2002-02-28
影响因子：
1.1
通讯作者：
Sciortino, M
中科院分区：
文献类型：
--
作者：
Mignosi, F;Restivo, A;Sciortino, M
给定有限或无限的单词v，我们考虑了第v的最小禁止因素的集合m（v），我们表明集合m（v）对于确定单词v的结构至关重要。有限的单词，我们考虑了两个与M（W）大小相关的参数：第一个计算W的最小禁止因子，第二个给出了W的最小长度，最小的最小禁止因子W。我们为这两个参数得出了尖锐的上限和下限。我们还证明第二个参数与单词w的最小周期有关。我们对算法的观点更感兴趣。实际上，我们针对以下两个问题设计了线性时间算法：（i）给定w，构造集合m（w），相反，（ii）给定m（w），重建单词。对于无限单词x，我们考虑以下两个函数：对于每个n，g（x），对于每个n，x的X的允许因子为n和f（x）的x，对于每个n，对于每个n来说，最小的禁止禁止长度为x的因子。我们解决以下一般问题：有关X结构的哪些信息可以从对（g（x），f（x））中得出？我们证明，这两个功能是表征的，直到交换两个字母的自动形态，即每个无限sturmian单词的因素的语言。 （c）2002 Elsevier Science B.V.保留所有权利。
Given a finite or infinite word v, we consider the set M(v) of minimal forbidden factors of v. We show that the set M(v) is of fundamental importance in determining the structure of the word v. In the case of a finite word it, we consider two parameters that are related to the size of M(w): the first counts the minimal forbidden factors of w and the second gives the length of the longest minimal forbidden factor of w. We derive sharp upper and lower bounds for both parameters. We prove also that the second parameter is related to the minimal period of the word w. We are further interested to the algorithmic point of view. Indeed, we design linear time algorithm for the following two problems: (i) given w, construct the set M(w) and, conversely, (ii) given M(w), reconstruct the word it,. In the case of an infinite word x, we consider the following two functions: g(x) that counts, for each n, the allowed factors of x of length n and f(x) that counts, for each n, the minimal forbidden factors of x of length n. We address the following general problem: what information about the structure of x can be derived from the pair (g(x), f(x))? We prove that these two functions characterize, up to the automorphism exchanging the two letters, the language of factors of each single infinite Sturmian word. (C) 2002 Elsevier Science B.V. All rights reserved.