Combinatorics on Words: 10th International Conference, WORDS 2015, Kiel, Germany, September 14-17, 2015, Proceedings (Lecture Notes in Computer Science Book 9304)

This book constitutes the refereed proceedings of the 10th International Conference on Combinatorics on Words, WORDS 2015, held in Kiel, Germany, in September 2015 under the auspices of the EATCS. The 14 revised full papers presented were carefully reviewed and selected from 22 submissions. The main object in the contributions are words, finite or infinite sequences of symbols over a finite alphabet. The papers reflect both theoretical contributions related to combinatorial, algebraic, and algorithmic aspects of words, as well as to contributions presenting applications of the theory of words in other field of computer science, linguistics, biology, bioinformatics, or physics. Front Matter....Pages I-XVIII Degrees of Transducibility....Pages 1-13 Equality Testing of Compressed Strings....Pages 14-26 On the Contribution of WORDS to the Field of Combinatorics on Words....Pages 27-34 Codes and Automata in Minimal Sets....Pages 35-46 Thue–Morse Along Two Polynomial Subsequences....Pages 47-58 Canonical Representatives of Morphic Permutations....Pages 59-72 Linear-Time Computation of Prefix Table for Weighted Strings....Pages 73-84 New Formulas for Dyck Paths in a Rectangle....Pages 85-96 Ambiguity of Morphisms in a Free Group....Pages 97-108 The Degree of Squares is an Atom....Pages 109-121 Words with the Maximum Number of Abelian Squares....Pages 122-134 Arithmetics on Suffix Arrays of Fibonacci Words....Pages 135-146 Prefix-Suffix Square Completion....Pages 147-159 Square-Density Increasing Mappings....Pages 160-169 Mechanical Proofs of Properties of the Tribonacci Word....Pages 170-190 On Arithmetic Progressions in the Generalized Thue-Morse Word....Pages 191-196 A Square Root Map on Sturmian Words....Pages 197-209 Specular Sets....Pages 210-222 On the Tree of Ternary Square-Free Words....Pages 223-236 Back Matter....Pages 237-237