De Bruijn Sequences and Suffix Arrays: Analysis and Constructions

Konstantinos Limniotis (), Nicholas Kolokotronis () and Dimitrios Kotanidis ()
Additional contact information
Konstantinos Limniotis: Open University of Cyprus
Nicholas Kolokotronis: University of Peloponnese
Dimitrios Kotanidis: Open University of Cyprus

A chapter in Modern Discrete Mathematics and Analysis, 2018, pp 297-316 from Springer

Abstract: Abstract Binary De Bruijn sequences are studied in this work, by means of analysing the properties of their suffix arrays. More precisely, specific properties that are present in the suffix array of any binary De Bruijn sequence are proved; by this way, it is shown that building an appropriate array based on these properties is equivalent to constructing a De Bruijn sequence. Therefore, simultaneous construction of a De Bruijn sequence and its suffix array is possible, whereas any possible De Bruijn sequence can be theoretically obtained. It is also shown that known constructions of De Bruijn sequences, such as the method of cross-join pairs, can be facilitated by the use of suffix arrays.

Date: 2018
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-319-74325-7_15

Ordering information: This item can be ordered from
http://www.springer.com/9783319743257

DOI: 10.1007/978-3-319-74325-7_15

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().