Counting maximal-exponent factors in words (Q728262)

The paper investigates maximal exponent factors (MEFs) in words, that is, factors having the maximal exponent among all factors occurring in a square-free word. In particular, the authors improve both the upper and the lower bounds previously known on the number of MEF occurrences. A MEF is a factor of the form \(uvu\), where \(u\) and \(v\) are nonempty words, and \(u\) is called the border of the MEF. The authors prove that there are less than \(4n/b\) occurrences of MEFs with maximum-length border at least \(b\) in a length-\(n\) word (Theorem 7), and that there exist at most \(1.8n\) number of occurrences of MEFs in a word of length-\(n\) (Theorem 17). Moreover, they show that every length-\(n\) word contains at most \(n\) occurrences of MEFs whenever the length of these factors is not a multiple of their longest border (Theorem 20). The paper ends with a construction that generates a word having a ratio of \(5/6\) of MEF occurrences relative to its length, with the maximal exponent \(10/9\), thus improving on a previous result [the first two authors, J. Comput. Syst. Sci. 82, No. 3, 477--487 (2016; Zbl 1333.68303)].