Some characterizations of Sturmian words in terms of the lexicographic order
type: Item
instance of: scholarly article
zbMATH Open document ID: 1317.68137
author: Michelangelo Bucci
author: Alessandro De Luca
author: Luca Q. Zamboni
publication date: 2012-06-20T00:00:00Z
full work available at URL: https://arxiv.org/abs/1205.5946
full work available at URL: fulltext.html
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 11B85
zbMATH DE Number: 6048127
zbMATH Keywords: Sturmian words
zbMATH Keywords: lexicographic order
MaRDI profile type: Publication
arXiv ID: 1205.5946
arXiv classification: math.CO
arXiv classification: cs.DM
title: Some characterizations of Sturmian words in terms of the lexicographic order
published in: Fundamenta Informaticae
review text: The authors present some characterizations of infinite Sturmian words \(w\), over an ordered alphabet \(\{0, 1, \ldots, k\}\) where \(0 < 1 < \cdots < k\), in terms of the lexicographic order of their factors. They prove that \(w\) is Sturmian over \(\{0,1\}\) if and only if \(w\) satisfies the so-called ``Nice Factors Ordering property''. The authors give some equivalent formulations of this property, one of them being the following: for \(k=1\) and every lexicographically consecutive factors \(v\) and \(v'\) of \(w\) of equal length, there exist words \(\lambda\) and \(\mu\) over \(\{0,1\}\) such that \(v=\lambda 01 \mu\) and \(v' = \lambda 10 \mu\) or \(v = \lambda 0\) and \(v' = \lambda 1\). Under the additional hypotheses of recurrence and aperiodicity of \(w\), they prove that \(w\) is Sturmian if and only if for all factors \(v\) and \(v'\) of \(w\) of equal length, if \(v\) is lexicographically smaller than \(v'\) then the number of occurrences of \(1\) in \(v\) is no more than that number in \(v'\). Under these additional hypotheses, they also prove that \(w\) is Sturmian if and only if all lexicographically consecutive factors \(v\) and \(v'\) of \(w\) of equal length differ in at most two positions.
reviewed by: F. Blanchet-Sadri
description: scientific article; zbMATH DE number 6048127