The Sum of Exponents of Maximal Repetitions in Standard Sturmian Words

被引：0

作者：

Piatkowski, Marcin ^{[1
]}

机构：

[1] Nicholas Copernicus Univ, Fac Math & Comp Sci, Torun, Poland

来源：

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2013 | 2013年

关键词：

Sturmian words; repetitions; runs; algorithm; RUNS;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A maximal repetition is a non-extendable (with the same period) periodic segment in a string, in which the period repeats at least twice. In this paper we study problems related to the structure of maximal repetitions in standard Sturmian words and present the formulas for the sum of their exponents. Moreover, we show how to compute the sum of exponents of maximal repetitions in any standard Sturmian word in linear time with respect to the (total) size of its compressed representation. The presented formulas and algorithm can be easily modified to obtain the total run length of the word.

引用

页码：48 / 62

页数：15

共 17 条

[1]

Allouche J.P., 2003, Automatic sequences: Theory, applications, generalizations

[2]

Baturo P, 2013, ELECTRON J COMB, V20

[3] Compressed string-matching in standard Sturmian words [J].

Baturo, Pawel ;

Rytter, Wojciech .

THEORETICAL COMPUTER SCIENCE, 2009, 410 (30-32) :2804-2810

[4]

Berstel J, 2007, LECT NOTES COMPUT SC, V4728, P23

[5]

Crochemore M, 2008, LECT NOTES COMPUT SC, V5029, P290, DOI 10.1007/978-3-540-69068-9_27

[6]

Crochemore M, 2007, LECT NOTES COMPUT SC, V4708, P465

[7] Powers in Sturmian sequences [J].

Damanik, D ;

Lenz, D .

EUROPEAN JOURNAL OF COMBINATORICS, 2003, 24 (04) :377-390

[8] The index of Sturmian sequences [J].

Damanik, D ;

Lenz, D .

EUROPEAN JOURNAL OF COMBINATORICS, 2002, 23 (01) :23-29

[9] An asymptotic lower bound for the maximal number of runs in a string [J].

Franek, Frantisek ;

Yang, Qian .

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2008, 19 (01) :195-203

[10]

GLEN A., 2013, ARXIV13016568

← 1 2 →