Journal article
An abelian periodicity lemma
Theoretical Computer Science, Vol.656(B), pp.249-255
2015
Abstract
We write x≺yx≺y when x and y are vectors with each element of x less than or equal to the corresponding element of y and P(w)P(w) for the Parikh vector of a word w. A word w has abelian period p if it has the form u0u1⋯umum+1u0u1⋯umum+1 with |u0|≤p|u0|≤p, |ui|=p|ui|=p for i=1,…mi=1,…m and |um+1|≤p|um+1|≤p, and P(u0)≺PP(u0)≺P, P(u0)=PP(u0)=P for i=1,…,mi=1,…,m and P(um+1)≺PP(um+1)≺P for some vector P. Blanchet-Sadri et al. conjectured that if a word has abelian periods pd and qd , where gcd(p,q)=1gcd(p,q)=1, and length at least 2pqd−12pqd−1 then the number of distinct letters appearing in the word is at most d , and that under certain conditions the bound may be reduced to 2pqd−22pqd−2. We prove their conjecture.
Details
- Title
- An abelian periodicity lemma
- Authors/Creators
- J. Simpson (Author/Creator) - Curtin University
- Publication Details
- Theoretical Computer Science, Vol.656(B), pp.249-255
- Publisher
- Elsevier BV
- Identifiers
- 991005540491707891
- Copyright
- © 2016 Published by Elsevier B.V.
- Murdoch Affiliation
- School of Engineering and Information Technology
- Language
- English
- Resource Type
- Journal article
Metrics
84 Record Views
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Citation topics
- 9 Mathematics
- 9.28 Pure Maths
- 9.28.534 Dynamical Systems
- Web Of Science research areas
- Computer Science, Theory & Methods
- ESI research areas
- Computer Science