Paper Info
Title
Finite-state independence.
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 … where = for every . This construction has its own interest.
Year
DOI
Venue
2018
https://doi.org/10.1007/s00224-017-9821-6
Theory of Computing Systems
Keywords
DocType
Volume
Finite-state automata,Infinite sequences,Normal sequences,Independence
Journal
abs/1611.03921
Issue
Citations 
PageRank 
7
0
0.34
References 
Authors
0
3
Name
Order
Citations
PageRank
Verónica Becher112122.89
Olivier Carton238140.97
Pablo Ariel Heiber3508.38