Mostrar el registro sencillo del ítem

dc.contributor.author
Becher, Veronica Andrea  
dc.contributor.author
Carton, Olivier  
dc.contributor.author
Heiber, Pablo Ariel  
dc.date.available
2018-09-18T18:41:39Z  
dc.date.issued
2018-10  
dc.identifier.citation
Becher, Veronica Andrea; Carton, Olivier; Heiber, Pablo Ariel; Finite-State Independence; Springer; Theory Of Computing Systems; 62; 7; 10-2018; 1555-1572  
dc.identifier.issn
1432-4350  
dc.identifier.uri
http://hdl.handle.net/11336/60112  
dc.description.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 x1x2x3… where x2n = xn for every n. This construction has its own interest.  
dc.format
application/pdf  
dc.language.iso
eng  
dc.publisher
Springer  
dc.rights
info:eu-repo/semantics/openAccess  
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/  
dc.subject
Finite-State Automata  
dc.subject
Independence  
dc.subject
Infinite Sequences  
dc.subject
Normal Sequences  
dc.subject.classification
Ciencias de la Computación  
dc.subject.classification
Ciencias de la Computación e Información  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
dc.title
Finite-State Independence  
dc.type
info:eu-repo/semantics/article  
dc.type
info:ar-repo/semantics/artículo  
dc.type
info:eu-repo/semantics/publishedVersion  
dc.date.updated
2018-09-17T19:37:52Z  
dc.journal.volume
62  
dc.journal.number
7  
dc.journal.pagination
1555-1572  
dc.journal.pais
Alemania  
dc.journal.ciudad
Berlin  
dc.description.fil
Fil: Becher, Veronica Andrea. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina  
dc.description.fil
Fil: Carton, Olivier. Université Paris Diderot - Paris 7; Francia  
dc.description.fil
Fil: Heiber, Pablo Ariel. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina  
dc.journal.title
Theory Of Computing Systems  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/https://dx.doi.org/10.1007/s00224-017-9821-6  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://link.springer.com/article/10.1007/s00224-017-9821-6  

Archivos asociados
Thumbnail
 
Tamaño: 295.9Kb
Formato: PDF
.