De Bruijn sequences and De Bruijn graphs for a general language

Author	dc.contributor.author	Moreno Araya, Eduardo
Admission date	dc.date.accessioned	2014-01-07T19:41:49Z
Available date	dc.date.available	2014-01-07T19:41:49Z
Publication date	dc.date.issued	2005
Cita de ítem	dc.identifier.citation	Information Processing Letters 96 (2005) 214–219	en_US
Identifier	dc.identifier.other	doi:10.1016/j.ipl.2005.05.028
Identifier	dc.identifier.uri	https://repositorio.uchile.cl/handle/2250/126018
General note	dc.description	Artículo de publicación ISI	en_US
Abstract	dc.description.abstract	A de Bruijn sequence over a finite alphabet of span n is a cyclic string such that all words of length n appear exactly once as factors of this sequence. We extend this definition to a subset of words of length n, characterizing for which subsets exists a de Bruijn sequence.We also study some symbolic dynamical properties of these subsets extending the definition to a language defined by forbidden factors. For these kinds of languages we present an algorithm to produce a de Bruijn sequence. In this work we use graph-theoretic and combinatorial concepts to prove these results.	en_US
Lenguage	dc.language.iso	en
Type of license	dc.rights	Attribution-NonCommercial-NoDerivs 3.0 Chile	*
Link to License	dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/3.0/cl/	*
Keywords	dc.subject	De Bruijn sequences	en_US
Título	dc.title	De Bruijn sequences and De Bruijn graphs for a general language	en_US
Document type	dc.type	Artículo de revista

Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile