| Description |
1 online resource illustrations |
|
text txt rdacontent |
|
computer c rdamedia |
|
online resource cr rdacarrier |
| Bibliography |
Includes bibliographical references and index. |
| Contents |
Front Cover -- Sequences and the de Bruijn Graph -- Copyright -- Contents -- Preface -- 1 Introduction -- 1.1 Some concepts in finite fields and number theory -- 1.2 Codes, graphs, and sequences -- 1.3 The de Bruijn graph and feedback shift registers -- 1.4 Overview of the chapters -- 1.5 Notes -- References -- 2 LFSR sequences -- 2.1 Sequence length and polynomial representation -- 2.2 Maximum length linear shift-register sequences -- 2.3 Powers of irreducible polynomials -- 2.4 Patterns with distinct differences -- 2.5 Notes -- References -- 3 Cycles and the nonlinear theory |
|
3.1 Cycles from feedback shift registers -- 3.2 Enumeration methods for polynomials and cycles -- 3.3 Maximum number of cycles in a state diagram -- 3.4 Notes -- References -- 4 Constructions of full cycles -- 4.1 Enumeration of all Eulerian cycles -- 4.2 The D-morphism and recursive constructions -- 4.3 Merging cycles of large factors -- 4.4 Notes -- References -- 5 Linear complexity of sequences -- 5.1 Binary sequences whose length is 2n -- 5.2 Complexity of binary de Bruijn sequences -- 5.3 Sequences over pm whose length is pn, p prime -- 5.4 Complexity of non-binary de Bruijn sequences |
|
5.5 Notes -- References -- 6 Classification of sequences -- 6.1 Classification of sequences with length 2n−1 -- 6.2 Classification of de Bruijn sequences -- 6.3 Classification of balanced sequences -- 6.4 The depth of a word -- 6.5 Notes -- References -- 7 One-dimensional applications -- 7.1 Stream ciphers -- 7.2 VLSI testing -- 7.3 Single-track Gray codes -- 7.4 Rotating-table games -- 7.5 Notes -- References -- 8 DNA sequences and DNA codes -- 8.1 The genome assembly -- 8.2 DNA storage codes -- 8.3 Constant-weight de Bruijn sequences -- 8.4 Reconstruction of a sequence from subsequences |
|
8.5 Synchronization codes -- 8.6 Notes -- References -- 9 Two-dimensional arrays -- 9.1 Graph representations of perfect maps -- 9.2 Constructions by merging cycles -- 9.3 Pseudo-random arrays -- 9.4 Recursive constructions for perfect maps -- 9.5 Two-dimensional arrays with distinct differences -- 9.6 Notes -- References -- 10 Two-dimensional applications -- 10.1 Robust self-location two-dimensional patterns -- 10.2 Key predistribution for sensor networks -- 10.3 Folding of one-dimensional sequences -- 10.4 Notes -- References -- 11 Unique path property graphs |
|
11.1 Basic properties of UPP graphs -- 11.2 Constructions for UPP graphs -- 11.3 Cycles and factors in UPP graphs -- 11.4 Notes -- References -- 12 Interconnection networks -- 12.1 The shuffle-exchange network -- 12.2 Multistage interconnection networks -- 12.3 Multistage permutation networks -- 12.4 Layouts -- 12.5 Notes -- References -- Index -- Back Cover |
| Summary |
The de Bruijn graph was defined in 1949 to enumerate the number of closed sequences where each n-tuple appears exactly once as a window in a sequence. Through the years, the graph and its sequences have found numerous applications – in space technology, wireless communication, cryptography, parallel computation, genome assembly, DNA storage, and microbiome research, among others. Sequences and the de Bruijn Graph: Properties, Constructions, and Applications explores the foundations of theoretical mathematical concepts and the important applications to computer science, electrical engineering, and bioinformatics. The book introduces the various concepts, ideas, and techniques associated with the use of the de Bruijn Graph, providing comprehensive coverage of sequence classification, one-dimensional and two-dimensional applications, graphs, interconnected networks, layouts, and embedded systems. Researchers, graduate students, professors, and professionals working in the fields of applied mathematics, electrical engineering, computer science and bioinformatics will find this book useful. Investigates computational and engineering applications associated with the de Bruijn graph, its sequences, and their generalizationExplores one-dimensional and two-dimensional sequences with special properties and their various properties and applicationsIntroduces the rich structure of the de Bruijn graph and its sequences, in both mathematical theory and its applications to computing and engineering problems. |
| Subject |
Sequences (Mathematics)
|
|
Suites (Mathématiques)
|
| Other Form: |
Original 0443135177 9780443135170 (OCoLC)1405364454 |
| ISBN |
9780443135187 (electronic bk.) |
|
0443135185 (electronic bk.) |
|
9780443135170 |
|
0443135177 |
| Standard No. |
AU@ 000076248453 |
|
