Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

An abelian periodicity lemma

Simpson, J. (2015) An abelian periodicity lemma. Theoretical Computer Science, 656 (B). pp. 249-255.

Link to Published Version: http://dx.doi.org/10.1016/j.tcs.2015.12.014
*Subscription may be required

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.

Item Type: Journal Article
Murdoch Affiliation: School of Engineering and Information Technology
Publisher: Elsevier BV
Copyright: © 2016 Published by Elsevier B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/29575
Item Control Page Item Control Page