Factorization forests for infinite words and applications to countable scattered linear orderings

摘要

The theorem of factorization forests of Imre Simon shows the existence of nested factorizations - 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. Second, we extend it to 'every linear ordering'. We use this last variant in a simplified proof of the translation of recognizable languages over countable scattered linear orderings to languages accepted by automata.