Factorisation Forests for Infinite Words Application to Countable Scattered Linear Orderings

摘要

The theorem of factorisation forests shows the existence of nested factorisations - a la Ramsey - for finite words. This theorem has important applications in semigroup theory, and beyond. We provide two improvements to the standard result. First we improve on all previously known bounds for the standard theorem. Second, we extend it to every 'complete linear ordering'. We use this variant in a simplified proof of complementation of automata over words of countable scattered domain.