2007/01/17 by Thomas Colcombet, Colcombet, Thomas
Computer Science · #Computability, Logic, AI Algorithms #F.4 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #cs.LO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.cs/0701113
27 pages
arxiv created 2007/01/17 · openalex publication_date 2007/01/17 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. The purpose of this paper is to illustrate the importance of this approach in the context of automata over infinite words and trees. We extend the theorem of factorisation forest in two directions: we show that it is still valid for any word indexed by a linear ordering; and we show that it admits a deterministic variant for words indexed by well-orderings. A byproduct of this work is also an improvement on the known bounds for the original result. We apply the first variant for giving a simplified proof of the closure under complementation of rational sets of words indexed by countable scattered linear orderings. We apply the second variant in the analysis of monadic second-order logic over trees, yielding new results on monadic interpretations over trees. Consequences of it are new caracterisations of prefix-recognizable structures and of the Caucal hierarchy.