2026/02/26 by Subin Pulari · 1 voice
Computer Science · #Asynchronous communication #Characterization (materials science) #Complexity and Algorithms in Graphs #Deterministic automaton #Deterministic finite automaton #Finite set #Independence (probability theory) #Machine Learning and Algorithms #Shuffling #Word (group theory) #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2602.23030
published in Open MIND
openalex publication_date 2026/02/26 · arxiv published 2026/02/26 · arxiv updated 2026/02/26 · openalex created_date 2026/02/28 · openalex updated_date 2026/07/28
Finite-state independence is a robust notion of algorithmic independence for infinite words. It was introduced for general infinite words by Becher, Carton, and Heiber via deterministic asynchronous two-tape finite automata. Álvarez, Becher, and Carton then studied the normal case and characterized finite-state independence in terms of deterministic finite-state shufflers. A shuffler is a finite automaton that reads from two input tapes x,y∈Σ^∞ and, at each step, chooses one tape to read next, outputs the symbol read, and updates its state based only on that output symbol. In terms of this characterization, two normal sources are finite-state independent if every deterministic finite-state way of shuffling (interleaving) them still produces a normal sequence. Álvarez, Becher, and Carton posed the following questions: (1) can one compute finite-state independent normal pairs efficiently, improving their doubly-exponential procedure; and (2) given a normal word x, can one effectively construct a normal word y that is finite-state independent from x? We answer both questions by explicit deterministic constructions. First, we give a deterministic polynomial-time algorithm that, on input N, outputs the first N symbols of two normal words x and y such that for every shuffler S, the shuffled output S(x,y) is normal; hence (x,y) is finite-state independent. Second, we solve the one-sided companion problem effectively. Given any computable normal word x∈Σ^∞, we give an explicit deterministic construction of a computable normal word y∈Σ^∞ such that for every shuffler S, the shuffled output S(x,y) is normal. In particular, x and y are finite-state independent by the shuffler characterization theorem.