Słowo Lyndona lub słowo pierwsze – niepuste słowo spełniające dwa warunki: jest pierwotne, tzn. nie można go przedstawić w postaci potęgi dla , wśród swoich cyklicznych obrotów jest najmniejsze względem porządku leksykograficznego
Przykładowo dla alfabetu można utworzyć 8 słów Lyndona nie dłuższych niż 4 litery ułożonych w porządku leksykograficznym: .
Twierdzenia Twierdzenie 1 Słowo jest słowem Lyndona wtedy i tylko wtedy, gdy jest niepuste i jest wcześniejsze w porządku leksykograficznym niż każdy jego sufiks właściwy. Twierdzenie 2 Słowo jest słowem Lyndona wtedy i tylko wtedy, gdy jest słowem jednoliterowym lub da się przedstawić jako złożenie dwóch słów Lyndona, w którym pierwsze słowo jest wcześniejsze w porządku leksykograficznym niż drugie. Powyższe dwa twierdzenia pozwalają sformułować dwie nowe definicje słowa Lyndona równoważne definicji ze wstępu.
Twierdzenie 3 Dowolne słowo można podzielić na słowa Lyndona a rozkład ten jest jednoznaczny jeśli spełnia warunek monotoniczności . W literaturze wynik takiego podziału jest nazywany rozkładem Lyndona () lub rozkładem standardowym (ang. ). Twierdzenie 4 Rozkład Lyndona można wyznaczyć w czasie liniowym.
Historia