On the permutation complexity of the Cantor-like sequences

被引：2

作者：

Lu, Xiao-Tao ^{[1
]}

Chen, Jin ^{[2
]}

Guo, Ying-Jun ^{[2
]}

Wen, Zhi-Xiong ^{[1
]}

机构：

[1] Huazhong Univ Sci & Technol, Dept Math & Stat, Wuhan 430074, Peoples R China

[2] Huazhong Agr Univ, Coll Sci, Wuhan 430070, Peoples R China

来源：

THEORETICAL COMPUTER SCIENCE | 2016年 / 616卷

基金：

中国国家自然科学基金;

关键词：

Cantor-like sequence; Factor complexity; Permutation complexity; Regular sequence; DFAO; K-REGULAR SEQUENCES; THUE-MORSE WORD; INFINITE PERMUTATIONS; AUTOMATIC SEQUENCES; RING;

D O I：

10.1016/j.tcs.2015.12.022

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper, we give a precise formula for the permutation complexity of Cantor-like sequences, which are non-uniformly recurrent automatic sequences. Since the sequences are automatic, as it was proved by Charlier et al. in 2012, the permutation complexity of each of them is a regular sequence. We give a precise recurrence relation and a generalized automaton for it. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：100 / 110

页数：11

共 20 条

[1] THE RING OF K-REGULAR SEQUENCES [J].

ALLOUCHE, JP ;

SHALLIT, J .

THEORETICAL COMPUTER SCIENCE, 1992, 98 (02) :163-197

[2]

Allouche JP, 2003, THEOR COMPUT SCI, V307, P3, DOI 10.1016/S0324-3975(03)00090-2

[3]

ALLOUCHE JP, 2003, AUTOMATIC SEQUENCE T

[4]

Berthe V., 2010, Encyclopedia of Mathematics and its Applications, V135

[5] Complexity and special factors [J].

Cassaigne, J .

BULLETIN OF THE BELGIAN MATHEMATICAL SOCIETY-SIMON STEVIN, 1997, 4 (01) :67-88

[6] ENUMERATION AND DECIDABLE PROPERTIES OF AUTOMATIC SEQUENCES [J].

Charlier, Emilie ;

Rampersad, Narad ;

Shallit, Jeffrey .

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2012, 23 (05) :1035-1066

[7]

Deviatov R., ARXIV150202310

[8]

Deviatov R, 2008, LECT NOTES COMPUT SC, V5010, P146, DOI 10.1007/978-3-540-79709-8_17

[9] On periodicity and low complexity of infinite permutations [J].

Fon-Der-Flaass, D. G. ;

Frid, A. E. .

EUROPEAN JOURNAL OF COMBINATORICS, 2007, 28 (08) :2106-2114

[10]

Frid A., 1998, STACS 98

← 1 2 →