2025/11/27 by Francesco Dolce, Dolce, Francesco, Hughes, Christian B.
Computer Science · #37B10 #37E05 #68R15 #Discrete Mathematics (cs.DM) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Logic, programming, and type systems #Polynomial and algebraic computation #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2511.22588
openalex publication_date 2025/11/27 · openalex created_date 2025/12/03 · openalex updated_date 2026/07/28
Branching Rauzy induction is a two-sided form of Rauzy induction that acts on regular interval exchange transformations (IETs). We introduce an extended form of branching Rauzy induction that applies to arbitrary standard IETs, including non-minimal ones. The procedure generalizes the branching Rauzy method with two induction steps, merging and splitting, to handle equal-length cuts and invariant components respectively. As an application, we show, via a stepwise morphic argument, that all return words in the language of an arbitrary IET cluster in the Burrows-Wheeler sense.