Finite-state independence

2016/11/12 by Verónica Becher, Olivier Carton, Becher, Verónica +3 · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1611.03921

openalex publication_date 2016/11/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this work we introduce a notion of independence based on finite-state automata: two infinite words are independent if no one helps to compress the other using one-to-one finite-state transducers with auxiliary input. We prove that, as expected, the set of independent pairs of infinite words has Lebesgue measure 1. We show that the join of two independent normal words is normal. However, the independence of two normal words is not guaranteed if we just require that their join is normal. To prove this we construct a normal word x₁x₂x₃… where x_2n=x_n for every n.

Citations

• Conditional probabilities and van Lambalgen theorem revisited

Cited by

• Multihead Finite-State Compression
• Multi-Head Finite-State Dimension

Related

• Finite-state Independence and Normal Sequences
• Preservation of normality by transducers
• A new upper bound for separating words
• A Sharper Upper Bound for the Separating Words Problem
• From Two-Way to One-Way Finite State Transducers