ICC 25427
INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Unidad Ejecutora - UE
artículos
Título:
Finite state independence
Autor/es:
OLIVIER CARTON ; VERÓNICA BECHER; PABLO ARIEL HEIBER
Revista:
THEORY OF COMPUTING SYSTEMS
Editorial:
SPRINGER
Referencias:
Lugar: Berlin; Año: 2017
ISSN:
1432-4350
Resumen:
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 x1x2x3 ... where x2n = xn for every n.
