| Home |
| About |
| Submission |
| Updating Entries |
| Using Entries |
| Search |
| Statistics |
| Index |
| Download |
Lyndon words
| Title: | Lyndon words |
| Authors: | Štěpán Holub and Štěpán Starosta |
| Submission date: | 2021-05-24 |
| Abstract: | Lyndon words are words lexicographically minimal in their conjugacy class. We formalize their basic properties and characterizations, in particular the concepts of the longest Lyndon suffix and the Lyndon factorization. Most of the work assumes a fixed lexicographical order. Nevertheless we also define the smallest relation guaranteeing lexicographical minimality of a given word (in its conjugacy class). |
| BibTeX: |
@article{Combinatorics_Words_Lyndon-AFP,
author = {Štěpán Holub and Štěpán Starosta},
title = {Lyndon words},
journal = {Archive of Formal Proofs},
month = may,
year = 2021,
note = {\url{https://isa-afp.org/entries/Combinatorics_Words_Lyndon.html},
Formal proof development},
ISSN = {2150-914x},
}
|
| License: | BSD License |
| Depends on: | Combinatorics_Words, Szpilrajn |
| Status: [ok] | This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations. |
|
Proof outline Proof document |
| Browse theories |
| Download this entry |