| Description |
1 online resource : illustrations (some color) |
| Series |
Lecture notes in computer science, 0302-9743 ; 11682 |
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues |
|
Lecture notes in computer science ; 11682.
|
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
|
| 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 |
| Summary |
This book constitutes the refereed proceedings of the 12th International Conference on Combinatorics on Words, WORDS 2019, held in Loughborough, UK, in September 2019. The 21 revised full papers presented in this book together with 5 invited talks were carefully reviewed and selected from 34 submissions. WORDS is the main conference series devoted to the mathematical theory of words. In particular, the combinatorial, algebraic and algorithmic aspects of words are emphasized. Motivations may also come from other domains such as theoretical computer science, bioinformatics, digital geometry, symbolic dynamics, numeration systems, text processing, number theory, etc. -- Provided by publisher |
| Bibliography |
Includes bibliographical references and author index |
| Notes |
Online resource; title from PDF title page (SpringerLink, viewed September 16, 2019) |
| Subject |
Combinatorial analysis -- Congresses
|
|
Word problems (Mathematics) -- Congresses
|
|
Combinatorial analysis
|
|
Word problems (Mathematics)
|
| Genre/Form |
Electronic books
|
|
proceedings (reports)
|
|
Conference papers and proceedings
|
|
Conference papers and proceedings.
|
|
Actes de congrès.
|
| Form |
Electronic book
|
| Author |
Mercaş, Robert, editor
|
|
Reidenbach, Daniel, editor
|
| ISBN |
9783030287962 |
|
3030287963 |
|
3030287955 |
|
9783030287955 |
|
9783030287979 |
|
3030287971 |
|
