Finite-State Independence

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 L...

Descripción completa

Guardado en:

Detalles Bibliográficos
Publicado:	2018
Materias:	Finite-state automata Independence Infinite sequences Normal sequences Computer science Finite automata Mathematical techniques Auxiliary inputs Finite state Finite state transducers Infinite word Lebesgue measure Automata theory
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14324350_v62_n7_p1555_Becher http://hdl.handle.net/20.500.12110/paper_14324350_v62_n7_p1555_Becher
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_14324350_v62_n7_p1555_Becher
record_format	dspace
spelling	paper:paper_14324350_v62_n7_p1555_Becher2023-06-08T16:14:09Z Finite-State Independence Finite-state automata Independence Infinite sequences Normal sequences Computer science Finite automata Mathematical techniques Auxiliary inputs Finite state Finite state transducers Independence Infinite sequences Infinite word Lebesgue measure Normal sequences Automata theory 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. This construction has its own interest. © 2017, Springer Science+Business Media, LLC. 2018 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14324350_v62_n7_p1555_Becher http://hdl.handle.net/20.500.12110/paper_14324350_v62_n7_p1555_Becher
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Finite-state automata Independence Infinite sequences Normal sequences Computer science Finite automata Mathematical techniques Auxiliary inputs Finite state Finite state transducers Independence Infinite sequences Infinite word Lebesgue measure Normal sequences Automata theory
spellingShingle	Finite-state automata Independence Infinite sequences Normal sequences Computer science Finite automata Mathematical techniques Auxiliary inputs Finite state Finite state transducers Independence Infinite sequences Infinite word Lebesgue measure Normal sequences Automata theory Finite-State Independence
topic_facet	Finite-state automata Independence Infinite sequences Normal sequences Computer science Finite automata Mathematical techniques Auxiliary inputs Finite state Finite state transducers Independence Infinite sequences Infinite word Lebesgue measure Normal sequences Automata theory
description	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. This construction has its own interest. © 2017, Springer Science+Business Media, LLC.
title	Finite-State Independence
title_short	Finite-State Independence
title_full	Finite-State Independence
title_fullStr	Finite-State Independence
title_full_unstemmed	Finite-State Independence
title_sort	finite-state independence
publishDate	2018
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14324350_v62_n7_p1555_Becher http://hdl.handle.net/20.500.12110/paper_14324350_v62_n7_p1555_Becher
_version_	1768545388317376512

Finite-State Independence

Ejemplares similares