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 |
Files in this item
This item appears in the following Collection(s)
-
Artículos de revistas
Artículos de revistas