Algebraic combinatorics on words, M. Lothaire, (electronic resource)

Resource Information

The instance Algebraic combinatorics on words, M. Lothaire, (electronic resource) represents a material embodiment of a distinct intellectual or artistic creation found in University of Manitoba Libraries. This resource is a combination of several types including: Instance, Electronic.

Image

http://covers.openlibrary.org/b/isbn/9781107326019-M.jpg?default=false

Label

Algebraic combinatorics on words, M. Lothaire, (electronic resource)

Medium

electronic resource

Statement of responsibility

M. Lothaire

Instantiates

• Algebraic combinatorics on words

Publication

• Cambridge England | New York, Cambridge University Press, 2002

Note

Description based upon print version of record

Bibliography note

Includes bibliographical references (p. 473-496) and indexes

Carrier category

online resource

Carrier category code

cr

Content category

text

Content type code

txt

Contents

• Cover; Half Title; Series Page; Title; Copyright; Contents; Preface; CHAPTER 1 Finite and Infinite Words; 1.0. Introduction; 1.1. Semi groups; 1.2. Words; 1.2.1. Finite words; 1.2.2. Infinite words; 1.2.3. Two-sided infinite words; 1.3. Automata; 1.3.1. Definitions; 1.3.2. Automata on infinite words; 1.3.3. Transducers; 1.3.4. Factor graphs; 1.4. Generating series; 1.5. Symbolic dynamical systems; 1.5.1. Definitions; 1.5.2. Recurrence and minimality; 1.5.3. Entropy; 1.6. Unavoidable sets; 1.6.1. Definitions and elementary properties; 1.6.2. The structure theorem; Problems; Section 1.1
• Section 1.2Section 1.3; Section 1.4; Section 1.5; Notes; CHAPTER 2 Sturmian Words; 2.0. Introduction; 2.1. Equivalent definitions; 2.1.1. Complexity and balance; 2.1.2. Mechanical words, rotations; 2.1.3. The factors of one Sturmian word; 2.2. Standard words; 2.2.1. Standard words and palindrome words; 2.2.2. Standard sequences and characteristic words; 2.2.3. Frequencies; 2.3. Sturmian morphisms; 2.3.1. A set of generators; 2.3.2. Standard morphisms; 2.3.3. A presentation of the monoid of Sturm; 2.3.4. Conjugate morphisms; 2.3.5. Automorphisms of the free group; 2.3.6. Fixed points; Problems
• Section 2.1Section 2.2; Section 2.3; Notes; CHAPTER 3 Unavoidable Patterns; 3.0. Introduction; 3.1. Definitions and basic properties; 3.1.1. Patterns and avoidability; 3.1.2. Powers; 3.1.3. Sesquipowers; 3.2. Deciding avoidability: the Zimin algorithm; 3.2.1. Reduction of patterns; 3.2.2. Reducible patterns are unavoidable; 3.2.3. Irreducible patterns are avoidable; 3.3. Avoidability on a fixed alphabet; 3.3.1. The avoidability index; 3.3.2. The binary case; 3.3.3. A bound on the avoidability index; 3.3.4. A bound on the length of 2-unavoidable patterns; Problems; Section 3.1; Section 3.2
• Section 3.3Notes; CHAPTER 4 Sesquipowers; 4.0. Introduction; 4.1. Bi-ideal sequences; 4.2. Canonical factorizations; 4.3. Sesquipowers and recurrence; 4.4. Extensions of a theorem of Shirshov; 4.5. Finiteness conditions for semigroups; 4.5.1. Permutation property; 4.5.2. Iteration property; 4.5.3. Minimal conditions on principal bi-ideals; Problems; Section 4.1; Section 4.2; Section 4.3; Section 4.4; Section 4.5; Notes; CHAPTER 5 The Plactic Monoid; 5.0. Introduction; 5.1. Schensted's algorithm; 5.2. Greene's invariants and the plactic monoid; 5.3. The Robinson-Schensted-Knuth correspondence
• 5.4. Schur functions and the Littlewood-Richardson rule5.5. Coplactic operations; 5.6. Cyclage and canonical embeddings; Problems; Section 5.1; Section 5.2; Section 5.3; Section 5.4; Section 5.5; Section 5.6; Notes; CHAPTER 6 Codes; 6.0. Introduction; 6.1. X-factorizations; 6.1.1. Codes; 6.1.2. ω-Codes; 6.2. Defect; 6.2.1. Defect theorem; 6.2.2. Infinite words; 6.2.3. Consequences; 6.2.4. Composition of codes; 6.3. More defect; 6.3.1. ξ-Codes; 6.3.2. A particular class of codes; 6.3.3. Three-element codes; 6.4. A theorem of Schiitzenberger; Problems; Section 6.1; Section 6.2; Section 6.3
• Notes

Dimensions

unknown

Extent

1 online resource (522 p.)

Form of item

online

Isbn

9781107326019

Media category

computer

Media type code

c

Record ID

99148828304601651

Specific material designation

remote

System control number

• (CKB)2670000000343946
• (EBL)1179098
• (SSID)ssj0000893823
• (PQKBManifestationID)11932451
• (PQKBTitleCode)TC0000893823
• (PQKBWorkID)10906938
• (PQKB)11164233
• (UkCbUP)CR9781107326019
• (MiAaPQ)EBC1179098
• (EXLCZ)992670000000343946