De Bruijn sequences and De Bruijn graphs for a general language

Eduardo Moreno

doi:10.1016/j.ipl.2005.05.028

De Bruijn sequences and De Bruijn graphs for a general language

Eduardo Moreno

Faculty of Engineering and Science

Research output: Contribution to journal › Article › peer-review

13 Scopus citations

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.

Original language	English
Pages (from-to)	214-219
Number of pages	6
Journal	Information Processing Letters
Volume	96
Issue number	6
DOIs	https://doi.org/10.1016/j.ipl.2005.05.028
State	Published - 31 Dec 2005

Keywords

Combinatorial problems
Combinatorics on words
De Bruijn graphs
De Bruijn sequences
Eulerian labeled graphs
Graph algorithms

Access to Document

10.1016/j.ipl.2005.05.028

Cite this

@article{10a26065dc6149c3b2e95d01019a427a,

title = "De Bruijn sequences and De Bruijn graphs for a general language",

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.",

keywords = "Combinatorial problems, Combinatorics on words, De Bruijn graphs, De Bruijn sequences, Eulerian labeled graphs, Graph algorithms",

author = "Eduardo Moreno",

note = "Funding Information: 1 Partially supported by ECOS C00E03 (French–Chilean Cooperation), Fundaci{\'o}n Andes and CONICYT Ph.D. Fellowship.",

year = "2005",

month = dec,

day = "31",

doi = "10.1016/j.ipl.2005.05.028",

language = "English",

volume = "96",

pages = "214--219",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - De Bruijn sequences and De Bruijn graphs for a general language

AU - Moreno, Eduardo

N1 - Funding Information: 1 Partially supported by ECOS C00E03 (French–Chilean Cooperation), Fundación Andes and CONICYT Ph.D. Fellowship.

PY - 2005/12/31

Y1 - 2005/12/31

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

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

KW - Combinatorial problems

KW - Combinatorics on words

KW - De Bruijn graphs

KW - De Bruijn sequences

KW - Eulerian labeled graphs

KW - Graph algorithms

UR - https://www.scopus.com/pages/publications/27644530544

U2 - 10.1016/j.ipl.2005.05.028

DO - 10.1016/j.ipl.2005.05.028

M3 - Article

AN - SCOPUS:27644530544

SN - 0020-0190

VL - 96

SP - 214

EP - 219

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

De Bruijn sequences and De Bruijn graphs for a general language

Abstract

Keywords

Access to Document

Fingerprint

Cite this