Linked e-resources
Details
Table of Contents
Intro; Preface; Organization; On Families of Limit \bi S -adic Words (Invited Talk); Contents; Matching Patterns with Variables; 1 Introduction; 2 Basic Definitions; 3 The Hardness of the Matching Problem; 4 Structural Restrictions for Patterns; 4.1 Pattern Matching by Graph Morphisms; 4.2 Efficiently Matchable Classes of Patterns; 4.3 Computing Structural Parameters for Patterns; 5 Faster Pattern Matching; 5.1 Patterns with Low Scope Coincidence Degree; 5.2 Patterns with Low Locality Number; 6 Efficient Pattern Matching Beyond Bounded Treewidth; 7 From Locality to Graph Parameters
8 Extensions8.1 Injectivity; 8.2 Word Equations; 9 Conclusions; References; Abelian Properties of Words; 1 Introduction; 2 Overview; 2.1 Definitions and Notation; 2.2 Abelian Complexity; 2.3 Abelian Avoidance; 2.4 Other Abelian Properties; 3 Small Abelian Complexity of Two-Dimensional Words; 3.1 Two-Dimensional Words; 3.2 Small Abelian Complexity of Recurrent Two-Dimensional Words; 3.3 Small Complexity of Uniformly Recurrent Two-Dimensional Words; 4 Abelian Subshifts; 4.1 Preliminaries and Notation; 4.2 On Abelian Subshifts of Binary Words
4.3 On Abelian Subshifts of Minimal Complexity Words and Related WordsReferences; On Sets of Words of Rank Two; 1 Introduction; 2 Preliminaries; 3 k-Maximal Monoids; 4 Primitive Sets; 5 Binary Root of a Single Primitive Word; 6 Connections with Pseudo-Primitive Words; References; Independent Systems of Word Equations: From Ehrenfeucht to Eighteen; 1 Introduction; 2 Preliminaries; 3 Ehrenfeucht's Conjecture; 4 Size of Independent Systems; 5 Recent Results; 6 Variations; References; Parikh Determinants; 1 Introduction; 2 Preliminaries; 3 Parikh Determinant of a Word; 4 Final Remarks
4.1 Parikh Determinant, Parikh Vector and Parikh Matrix4.2 An Alternative Way to Compute Parikh Determinants; 4.3 Generalization of Parikh Determinants; References; Critical Exponent of Infinite Balanced Words via the Pell Number System; 1 Introduction; 1.1 Preliminaries; 1.2 Previous Work; 1.3 Automatic Theorem Proving Using Walnut; 2 Building the Automata; 2.1 Pell Number System; 2.2 Automaton for the Addition Relation in Pell-Base; 2.3 Automaton for Computing x5; 3 Writing the Proof; 3.1 Proving the Hypothesis; 3.2 Exploring Interesting Properties; 4 Breadth-First Search
5 Future Prospects5.1 Other Words Characterized by Pell-Base; 5.2 Open Problems; References; Repetitions in Infinite Palindrome-Rich Words; 1 Introduction; 1.1 Preliminaries; 1.2 Previous Work; 2 Results over the Binary Alphabet; 2.1 Automatic Theorem-Proving; 2.2 Constructing the Automaton; 2.3 Proof of Equivalence of the Morphisms; 2.4 Proof of Palindromic Richness; 2.5 Determining the Critical Exponent; 2.6 Optimality of the Critical Exponent; 3 Faster Backtracking; 3.1 Lyndon Method; 3.2 Counting Palindromes; 3.3 Computing Maximal Runs; 4 Future Prospects; References
8 Extensions8.1 Injectivity; 8.2 Word Equations; 9 Conclusions; References; Abelian Properties of Words; 1 Introduction; 2 Overview; 2.1 Definitions and Notation; 2.2 Abelian Complexity; 2.3 Abelian Avoidance; 2.4 Other Abelian Properties; 3 Small Abelian Complexity of Two-Dimensional Words; 3.1 Two-Dimensional Words; 3.2 Small Abelian Complexity of Recurrent Two-Dimensional Words; 3.3 Small Complexity of Uniformly Recurrent Two-Dimensional Words; 4 Abelian Subshifts; 4.1 Preliminaries and Notation; 4.2 On Abelian Subshifts of Binary Words
4.3 On Abelian Subshifts of Minimal Complexity Words and Related WordsReferences; On Sets of Words of Rank Two; 1 Introduction; 2 Preliminaries; 3 k-Maximal Monoids; 4 Primitive Sets; 5 Binary Root of a Single Primitive Word; 6 Connections with Pseudo-Primitive Words; References; Independent Systems of Word Equations: From Ehrenfeucht to Eighteen; 1 Introduction; 2 Preliminaries; 3 Ehrenfeucht's Conjecture; 4 Size of Independent Systems; 5 Recent Results; 6 Variations; References; Parikh Determinants; 1 Introduction; 2 Preliminaries; 3 Parikh Determinant of a Word; 4 Final Remarks
4.1 Parikh Determinant, Parikh Vector and Parikh Matrix4.2 An Alternative Way to Compute Parikh Determinants; 4.3 Generalization of Parikh Determinants; References; Critical Exponent of Infinite Balanced Words via the Pell Number System; 1 Introduction; 1.1 Preliminaries; 1.2 Previous Work; 1.3 Automatic Theorem Proving Using Walnut; 2 Building the Automata; 2.1 Pell Number System; 2.2 Automaton for the Addition Relation in Pell-Base; 2.3 Automaton for Computing x5; 3 Writing the Proof; 3.1 Proving the Hypothesis; 3.2 Exploring Interesting Properties; 4 Breadth-First Search
5 Future Prospects5.1 Other Words Characterized by Pell-Base; 5.2 Open Problems; References; Repetitions in Infinite Palindrome-Rich Words; 1 Introduction; 1.1 Preliminaries; 1.2 Previous Work; 2 Results over the Binary Alphabet; 2.1 Automatic Theorem-Proving; 2.2 Constructing the Automaton; 2.3 Proof of Equivalence of the Morphisms; 2.4 Proof of Palindromic Richness; 2.5 Determining the Critical Exponent; 2.6 Optimality of the Critical Exponent; 3 Faster Backtracking; 3.1 Lyndon Method; 3.2 Counting Palindromes; 3.3 Computing Maximal Runs; 4 Future Prospects; References