Издательство Chapman & Hall/CRC, 2008, -391 pp.
biology, nano-technology, data communication, and DNA computing [104].
Partial words are currently being considered, in particular, for finding good encodings for DNA computations. Courses, covering different sets of topics, are already being taught at some universities. The time seems right for a book that develops, in a clear manner, some of the central ideas and results of this area, as well as sets the tone of research for the next several years. This book on algorithmic combinatorics on partial words addresses precisely this need.
An effort has been made to ensure that this book is able to serve as a textbook for a diversity of courses. It is intended as an upper-level undergraduate or introductory graduate text in algorithms and combinatorics. It contains a mathematical treatment of combinatorics on partial words designed around algorithms and can be used for teaching and research. The chapters not only cover topics in which definitive techniques have emerged for solving problems related to partial words but also cover topics in which progress is desired and expected over the next several years. The principal audience we have in mind for this book are undergraduate or beginning graduate students from the mathematical and computing sciences. This book will be of interest to students, researchers, and practitioners in discrete mathematics and theoretical computer science who want to lea about this new and exciting class of partial words where many problems still lay unexplored. It will also be of interest to students, researchers, and practitioners in bioinformatics, computational molecular biology, DNA computing, and Mathematical Linguistics seeking to understand this subject. We do assume that the reader has taken some first course in discrete mathematics.
Basics.
Preliminaries on Partial Words.
Combinatorial Properties of Partial Words.
Periodicity.
Fine and Wilf ’s Theorem.
Critical Factorization Theorem.
Guibas and Odlyzko’s Theorem.
Primitivity.
Primitive Partial Words.
Unbordered Partial Words.
Coding 223.
P-codes of Partial Words.
Deciding the Pcode Property.
Further topics.
Equations on Partial Words.
Correlations of Partial Words.
Unavoidable Sets of Partial Words.
Solutions to Selected Exercises.
biology, nano-technology, data communication, and DNA computing [104].
Partial words are currently being considered, in particular, for finding good encodings for DNA computations. Courses, covering different sets of topics, are already being taught at some universities. The time seems right for a book that develops, in a clear manner, some of the central ideas and results of this area, as well as sets the tone of research for the next several years. This book on algorithmic combinatorics on partial words addresses precisely this need.
An effort has been made to ensure that this book is able to serve as a textbook for a diversity of courses. It is intended as an upper-level undergraduate or introductory graduate text in algorithms and combinatorics. It contains a mathematical treatment of combinatorics on partial words designed around algorithms and can be used for teaching and research. The chapters not only cover topics in which definitive techniques have emerged for solving problems related to partial words but also cover topics in which progress is desired and expected over the next several years. The principal audience we have in mind for this book are undergraduate or beginning graduate students from the mathematical and computing sciences. This book will be of interest to students, researchers, and practitioners in discrete mathematics and theoretical computer science who want to lea about this new and exciting class of partial words where many problems still lay unexplored. It will also be of interest to students, researchers, and practitioners in bioinformatics, computational molecular biology, DNA computing, and Mathematical Linguistics seeking to understand this subject. We do assume that the reader has taken some first course in discrete mathematics.
Basics.
Preliminaries on Partial Words.
Combinatorial Properties of Partial Words.
Periodicity.
Fine and Wilf ’s Theorem.
Critical Factorization Theorem.
Guibas and Odlyzko’s Theorem.
Primitivity.
Primitive Partial Words.
Unbordered Partial Words.
Coding 223.
P-codes of Partial Words.
Deciding the Pcode Property.
Further topics.
Equations on Partial Words.
Correlations of Partial Words.
Unavoidable Sets of Partial Words.
Solutions to Selected Exercises.