Semantic Scholar Open Access 2018 27 sitasi

Constructing de Bruijn sequences with co-lexicographic order: The k-ary Grandmama sequence

Patrick Baxter Dragon Oscar I. Hernandez J. Sawada A. Williams Dennis Wong

Abstrak

Abstract A k -ary de Bruijn sequence of order n is a circular k -ary string of length k n which contains every k -ary string of length n exactly once as a substring. It is well-known that a k -ary de Bruijn sequence of order n can be constructed by concatenating the aperiodic prefixes of the k -ary necklaces of length n in lexicographic order. In this article we prove that an alternate de Bruijn sequence is created by replacing lexicographic order with co-lexicographic order. We also provide a simple successor rule for generating each successive symbol in O ( n ) -time.

Topik & Kata Kunci

Mathematics Computer Science

Penulis (5)

Patrick Baxter Dragon

Oscar I. Hernandez

J. Sawada

A. Williams

Dennis Wong

Format Sitasi

APA MLA BibTeX

Dragon, P.B., Hernandez, O.I., Sawada, J., Williams, A., Wong, D. (2018). Constructing de Bruijn sequences with co-lexicographic order: The k-ary Grandmama sequence. https://doi.org/10.1016/j.ejc.2018.03.006

Akses Cepat

PDF tidak tersedia langsung

Cek di sumber asli →

Lihat di Sumber doi.org/10.1016/j.ejc.2018.03.006

Informasi Jurnal

Tahun Terbit: 2018
Bahasa: en
Total Sitasi: 27×
Sumber Database: Semantic Scholar
DOI: 10.1016/j.ejc.2018.03.006
Akses: Open Access ✓