LyndonFactorization

Abstract

Every finite word factors into nonincreasing Lyndon words.

This module privately constructs the Chen-Fox-Lyndon factorization by inserting successive letters, joining adjacent factors when the required order fails. Its specification gives the original flattened word, Lyndonhood of every factor, and nonincreasing factor order for the recovery proof.

References

• Dependency: D5/S1/Words/Complexity/LyndonBrackets/LyndonOrder
• Dependency: D5/S1/Words/Complexity/VivionBinomialConverseFails