Algorithmic combinatorics on partial words. (©2008)

• Record Type: Book
• Further Information: Note: Francine Blanchet-Sadri.
• Other Names: Blanchet-Sadri, Francine
• Contents: 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 x m ↑ y n ; The equation x 2 ↑ y m z ; The equation x m y n ↑ z p ; 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.
• Publisher Details: Boca Raton, FL : Chapman & Hall/CRC
• Publication Date: 2008
• Copyright Date: 2008
• Extent: 1 online resource (385 pages), illustrations
• Subjects: 005.1; Computer algorithms; Computer science -- Mathematics; Combinatorial analysis; COMPUTERS -- Programming -- Open Source; COMPUTERS -- Software Development & Engineering -- Tools; COMPUTERS -- Software Development & Engineering -- General; Combinatorial analysis; Computer algorithms; Computer science -- Mathematics; Electronic books
• Languages: English
• ISBNs: 9781420060935; 1420060937; 9781420060928; 1420060929
• Notes: Note: Includes bibliographical references (pages 369-378) and index.; Note: Print version record.
• Access Rights: Legal Deposit; Only available on premises controlled by the deposit library and to one user at any one time; The Legal Deposit Libraries (Non-Print Works) Regulations (UK).
• Access Usage: Restricted: Printing from this resource is governed by The Legal Deposit Libraries (Non-Print Works) Regulations (UK) and UK copyright law currently in force.