Palindrome complexity

被引：79

作者：

Allouche, JP

Baake, M

Cassaigne, J

Damanik, D

机构：

[1] Univ Paris 11, CNRS, LRI, F-91405 Orsay, France

[2] Ernst Moritz Arndt Univ Greifswald, Inst Math & Informat, D-17487 Greifswald, Germany

[3] CNRS, IML, F-13288 Marseille 9, France

[4] CALTECH, Dept Math 25337, Pasadena, CA 91125 USA

来源：

THEORETICAL COMPUTER SCIENCE | 2003年 / 292卷 / 01期

关键词：

D O I：

10.1016/S0304-3975(01)00212-2

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study the palindrome complexity of infinite sequences on finite alphabets, i.e., the number of palindromic factors (blocks) of given length occurring in a given sequence. We survey the known results and obtain new results for some sequences, in particular for Rote sequences and for fixed points of primitive morphisms of constant length belonging to "class P" of Hof-Knill-Simon. We also give an upper bound for the palindrome complexity of a sequence in terms of its (block-)complexity. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：9 / 31

页数：23

共 49 条

[1]

Alessandri P., 1998, ENSEIGN MATH, V44, P103

[2]

Allouche J.-P., 2000, Discrete Mathematics & Theoretical Computer Science, V4

[3]

Allouche J.-P., 1994, B BELG MATH SOC, V1, P133

[4]

Allouche J.-P., 1994, B BELG MATH SOC-SIM, V1, P145