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

Occurrences of palindromes in characteristic Sturmian words

Glen, A.ORCID: 0000-0002-9434-3412 (2006) Occurrences of palindromes in characteristic Sturmian words. Theoretical Computer Science, 352 (1-3). pp. 31-46.

[img]
PDF - Authors' Version
Download (257kB)
Free to read: http://dx.doi.org/10.1016/j.tcs.2005.09.075
*No subscription required

Abstract

This paper is concerned with palindromes occurring in characteristic Sturmian words cα of slope α, where α∈(0,1) is an irrational. As cα is a uniformly recurrent infinite word, any (palindromic) factor of cα occurs infinitely many times in cα with bounded gaps. Our aim is to completely describe where palindromes occur in cα. In particular, given any palindromic factor u of cα, we shall establish a decomposition of cα with respect to the occurrences of u. Such a decomposition shows precisely where u occurs in cα, and this is directly related to the continued fraction expansion of α.

Item Type: Journal Article
Publisher: Elsevier BV
Copyright: © 2005 Elsevier B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/3880
Item Control Page Item Control Page

Downloads

Downloads per month over past year