Applied Combinatorics on Words

by M. Lothaire

• ISBN13: 9780521848022
• ISBN10: 0521848024
• Format: Hardcover
• Copyright: 2005-07-25
• Publisher: Cambridge University Press

Summary

A series of important applications of combinatorics on words has emerged with the development of computerized text and string processing. The aim of this volume, the third in a trilogy, is to present a unified treatment of some of the major fields of applications. After an introduction that sets the scene and gathers together the basic facts, there follow chapters in which applications are considered in detail. The areas covered include core algorithms for text processing, natural language processing, speech processing, bioinformatics, and areas of applied mathematics such as combinatorial enumeration and fractal analysis. No special prerequisites are needed, and no familiarity with the application areas or with the material covered by the previous volumes is required. The breadth of application, combined with the inclusion of problems and algorithms and a complete bibliography will make this book ideal for graduate students and professionals in mathematics, computer science, biology and linguistics.

Table of Contents

Preface	ix
Chapter 1 Algorithms on Words	1	(105)
1.0 Introduction	1	(2)
1.1 Words	3	(4)
1.2 Elementary algorithms	7	(8)
1.3 Tries and automata	15	(21)
1.4 Pattern matching	36	(4)
1.5 Transducers	40	(12)
1.6 Parsing	52	(17)
1.7 Word enumeration	69	(5)
1.8 Probability distributions on words	74	(17)
1.9 Statistics on words	91	(5)
Problems	96	(5)
Notes	101	(5)
Chapter 2 Structures for Indexes	106	(58)
2.0 Introduction	106	(1)
2.1 Suffix trie	107	(6)
2.2 Suffix tree	113	(8)
2.3 Contexts of factors	121	(6)
2.4 Suffix automaton	127	(11)
2.5 Compact suffix automaton	138	(3)
2.6 Indexes	141	(9)
2.7 Finding regularities	150	(5)
2.8 Pattern matching machine	155	(5)
Problems	160	(1)
Notes	161	(3)
Chapter 3 Symbolic Natural Language Processing	164	(46)
3.0 Introduction	164	(1)
3.1 From letters to words	165	(34)
3.2 From words to sentences	199	(9)
Notes	208	(2)
Chapter 4 Statistical Natural Language Processing	210	(31)
4.0 Introduction	210	(1)
4.1 Preliminaries	211	(2)
4.2 Algorithms	213	(13)
4.3 Application to speech recognition	226	(13)
Notes	239	(2)
Chapter 5 Inference of Network Expressions	241	(27)
5.0 Introduction	241	(1)
5.1 Inferring simple network expressions: models and related problems	242	(6)
5.2 Algorithms	248	(8)
5.3 Inferring network expressions with spacers	256	(4)
5.4 Related issues	260	(4)
5.5 Open problems	264	(1)
Notes	265	(3)
Chapter 6 Statistics on Words with Applications to Biological Sequences	268	(85)
6.0 Introduction	268	(2)
6.1 Probabilistic models for biological sequences	270	(7)
6.2 Overlapping and nonoverlapping occurrences	277	(4)
6.3 Word locations along a sequence	281	(8)
6.4 Word count distribution	289	(22)
6.5 Renewal count distribution	311	(4)
6.6 Occurrences and counts of multiple patterns	315	(13)
6.7 Some applications to DNA sequences	328	(10)
6.8 Some probabilistic and statistical tools	338	(8)
Notes	346	(7)
Chapter 7 Analytic Approach to Pattern Matching	353	(77)
7.0 Introduction	353	(3)
7.1 Probabilistic models	356	(3)
7.2 Exact string matching	359	(16)
7.3 Generalized string matching	375	(18)
7.4 Subsequence pattern matching	393	(14)
7.5 Generalized subsequence problem	407	(6)
7.6 Self-repetitive pattern matching	413	(12)
Problems	425	(2)
Notes	427	(3)
Chapter 8 Periodic Structures in Words	430	(48)
8.0 Introduction	430	(1)
8.1 Definitions and preliminary results	431	(2)
8.2 Counting maximal repetitions	433	(6)
8.3 Basic algorithmic tools	439	(4)
8.4 Finding all maximal repetitions in a word	443	(5)
8.5 Finding quasi-squares in two words	448	(2)
8.6 Finding repeats with a fixed gap	450	(4)
8.7 Computing local periods of a word	454	(7)
8.8 Finding approximate repetitions	461	(13)
Notes	474	(4)
Chapter 9 Counting, Coding, and Sampling with Words	478	(42)
9.0 Introduction	478	(2)
9.1 Counting: walks in sectors of the plane	480	(12)
9.2 Sampling: polygons, animals, and polyominoes	492	(12)
9.3 Coding: trees and maps	504	(12)
Problems	516	(2)
Notes	518	(2)
Chapter 10 Words in Number Theory	520	(59)
10.0 Introduction	520	(1)
10.1 Morphic and automatic sequences: definitions and generalities	521	(5)
10.2 d-Kernels and properties of automatic sequences	526	(10)
10.3 Christol's algebraic characterization of automatic sequences	536	(5)
10.4 An application to transcendence in positive characteristic	541	(2)
10.5 An application to transcendental power series over the rationals	543	(1)
10.6 An application to transcendence of real numbers	544	(2)
10.7 The Tribonacci word	546	(6)
10.8 The Rauzy fractai	552	(12)
10.9 An application to simultaneous approximation	564	(3)
Problems	567	(7)
Notes	574	(5)
References	579	(24)
General Index	603