E-Book, Englisch, 392 Seiten
Blanchet-Sadri Algorithmic Combinatorics on Partial Words
Erscheinungsjahr 2007
ISBN: 978-1-4200-6093-5
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)
E-Book, Englisch, 392 Seiten
Reihe: Discrete Mathematics and Its Applications
ISBN: 978-1-4200-6093-5
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)
The discrete mathematics and theoretical computer science communities have recently witnessed explosive growth in the area of algorithmic combinatorics on words. The next generation of research on combinatorics of partial words promises to have a substantial impact on molecular biology, nanotechnology, data communication, and DNA computing. Delving into this emerging research area, Algorithmic Combinatorics on Partial Words presents a mathematical treatment of combinatorics on partial words designed around algorithms and explores up-and-coming techniques for solving partial word problems as well as the future direction of research. This five-part book begins with a section on basics that covers terminology, the compatibility of partial words, and combinatorial properties of words. The book then focuses on three important concepts of periodicity on partial words: period, weak period, and local period. The next part describes a linear time algorithm to test primitivity on partial words and extends the results on unbordered words to unbordered partial words while the following section introduces some important properties of pcodes, details a variety of ways of defining and analyzing pcodes, and shows that the pcode property is decidable using two different techniques. In the final part, the author solves various equations on partial words, presents binary and ternary correlations, and covers unavoidable sets of partial words. Setting the tone for future research in this field, this book lucidly develops the central ideas and results of combinatorics on partial words.
Zielgruppe
Undergraduate and graduate students, researchers, and practitioners in discrete mathematics and theoretical computer science.
Autoren/Hrsg.
Fachgebiete
Weitere Infos & Material
preface
Basics
Preliminaries on Partial Words
Alphabets, letters, and words
Partial functions and partial words
Periodicity
Factorizations of partial words
Recursion and induction on partial words
Containment and compatibility
Combinatorial Properties of Partial Words
Conjugacy
Commutativity
PERIODICITY
Fine and Wilf’s Theorem
The case of zero or one hole
The case of two or three holes
Special partial words
Graphs associated with partial words
The main result
Related results
Critical Factorization Theorem
Orderings
The zero-hole case
The main result: First version
The main result: Second version
Tests
Guibas and Odlyzko’s Theorem
The zero-hole case
The main result
The algorithm
PRIMITIVITY
Primitive Partial Words
Testing primitivity on partial words
Counting primitive partial words
Exact periods
First counting method
Second counting method
Existence of primitive partial words
Unbordered Partial Words
Concatenations of prefixes
More results on concatenations of prefixes
Critical factorizations
Conjugates
CODING
Pcodes of Partial Words
Binary relations
Pcodes
Pcodes and monoids
Prefix and suffix orderings
Border ordering
Commutative ordering
Circular pcodes
Deciding the Pcode Property
First algorithm
Second algorithm
FURTHER TOPICS
Equations on Partial Words
The equation xm ? yn
The equation x2 ? ymz
The equation xmyn ? zp
Correlations of Partial Words
Binary and ternary correlations
Characterizations of correlations
Distributive lattices
Unavoidable Sets of Partial Words
Unavoidable sets
Classifying unavoidable sets of size two
The case where k = 1 and l = 1
The case where k = 1 and l = 2
Larger values of k and l
Solutions to Selected Exercises
References
Index
Numerous Exercises as well as Website and Bibliographic Notes appear at the end of each chapter.
