The Maximal Subword Complexity of Quasiperiodic Infinite Words

Details The Maximal Subword Complexity of Quasiperiodic Infinite Words The Maximal Subword Complexity of Quasiperiodic Infinite Words

2010-08-10

arxiv.org/abs/1008.1659v1

EPTCS 31, 2010, pp. 169-176

Computer Science

Formal Languages and Automata Theory

In Proceedings DCFS 2010, arXiv:1008.1270

Scientific paper

10.4204/EPTCS.31.19

We provide an exact estimate on the maximal subword complexity for quasiperiodic infinite words. To this end we give a representation of the set of finite and of infinite words having a certain quasiperiod q via a finite language derived from q. It is shown that this language is a suffix code having a bounded delay of decipherability. Our estimate of the subword complexity now follows from this result, previously known results on the subword complexity and elementary results on formal power series.

Affiliated with

Also associated with

No associations

Rating

The Maximal Subword Complexity of Quasiperiodic Infinite Words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Maximal Subword Complexity of Quasiperiodic Infinite Words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Maximal Subword Complexity of Quasiperiodic Infinite Words will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-583292