De Bruijn sequences and De Bruijn graphs for a general language

Author	dc.contributor.author	Moreno, Eduardo
Admission date	dc.date.accessioned	2007-05-22T21:30:00Z
Available date	dc.date.available	2007-05-22T21:30:00Z
Publication date	dc.date.issued	2005-12-31
Cita de ítem	dc.identifier.citation	INFORMATION PROCESSING LETTERS 96 (6): 214-219 DEC 31 2005	en
Identifier	dc.identifier.issn	0020-0190
Identifier	dc.identifier.uri	https://repositorio.uchile.cl/handle/2250/124628
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
Lenguage	dc.language.iso	en	en
Publisher	dc.publisher	ELSEVIER SCIENCE	en
Keywords	dc.subject	NECKLACES	en
Título	dc.title	De Bruijn sequences and De Bruijn graphs for a general language	en
Document type	dc.type	Artículo de revista