Periodicity and unbordered segments of words

✍ Scribed by Andrzej Ehrenfeucht; D.M. Silberger

• Publisher: Elsevier Science
• Year: 1979
• Tongue: English
• Weight: 987 KB
• Volume: 26
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(79)90116-x

✦ Synopsis

A nonempty word 0 is said to be a border of a word ar if and only if (Y = hp = @p for some nonempty words A and p. For an arbitrary (possibly infinite) sequence (II the expression #cu denotes the (possibly infinite) supremum of the set of all Ipj for /3 an u&ordered finite segment of (Y.

Principal Theorem. Let (II be infinite. Then the left segment T of (Y, for which ITI= #(Y, is the shorfest for which (II=TTT---=T~.

Theorem. Let a be finite. Let a be the longest proper that (II = 07 (CK = w). ?%en T also is unbordered. unbordered left (right) segment of a. Let T be such Theorem. Let (II be finite and not of the form 0" for n > 1. Let L be a letter in the word ~1. Then there exist words p and v such that cy = pLv while the word Lvp is unbordered.