Combinatorics on Words [[electronic resource] ] : 10th International Conference, WORDS 2015, Kiel, Germany, September 14-17, 2015, Proceedings / / edited by Florin Manea, Dirk Nowotka

• Record Nr.: UNISA996200359103316
• Pubbl/distr/stampa: Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015
• ISBN: 3-319-23660-1
• Edizione: [1st ed. 2015.]
• Descrizione fisica: 1 online resource (XVIII, 237 p. 47 illus.)
• Collana: Theoretical Computer Science and General Issues, , 2512-2029 ; ; 9304
• Disciplina: 511.6
• Soggetti: Machine theory; Computer science; Computer science—Mathematics; Discrete mathematics; Artificial intelligence; Software engineering; Formal Languages and Automata Theory; Theory of Computation; Discrete Mathematics in Computer Science; Artificial Intelligence; Software Engineering
• Lingua di pubblicazione: Inglese
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di contenuto: Intro -- Preface -- Organization -- Abstracts of Invited Talks -- Degrees of Transducibility -- Equality Testing of Compressed Strings -- On the Contribution of WORDS to the Field of Combinatorics on Words -- Codes and Automata in Minimal Sets -- Decidability of Abelian-Power-Freeness and Generalizations -- Thue-Morse Along Two Polynomial Subsequences -- Contents -- Degrees of Transducibility -- 1 Introduction -- 2 Preliminaries -- 2.1 Finite State Transducers and Mealy Machines -- 2.2 Degrees of Transducibility -- 3 Comparison -- 4 Atoms and Polynomials -- 5 A Plethora of Questions -- References -- Equality Testing of Compressed Strings -- 1 Introduction -- 2 Straight-Line Programs -- 3 Sequential Algorithms -- ; 4 A Parallel Algorithm -- 5 Related Problems -- 6 Open Problems -- References -- On the Contribution of WORDS to the Field of Combinatorics on Words -- References -- Codes and Automata in Minimal Sets -- 1 Introduction -- 2 Neutral and Tree Sets -- 2.1 Neutral Sets -- 2.2 Tree Sets -- 3 Automata -- 4 Codes -- 4.1 A Cardinality Theorem for Prefix Codes -- 4.2 The Group of a Bifix Code -- References -- Thue--Morse Along Two Polynomial Subsequences -- 1 Introduction -- 2 Thue--Morse at Distinct Multiples -- 3 Thue--Morse at Two Polynomials -- References -- Canonical Representatives of Morphic Permutations -- 1 Introduction -- 2 Basic Definitions -- 3 Ergodic Permutations -- 4 Ergodic Permutations Generated by Words -- 4.1 Morphisms on Words and Intervals -- References -- Linear-Time Computation of Prefix Table for Weighted Strings -- 1 Introduction -- 2 Properties and Auxiliary Data Structures -- 3 Algorithm -- 4 Final Remarks -- References -- New Formulas for Dyck Paths in a Rectangle -- 1 Introduction -- 2 Definitions and Notation -- 3 Ferrers Diagrams Comparison Method -- 3.1 Diagrams Decomposition Method -- 3.2 Technical Results.; 4 Theorems -- 5 Examples -- 5.1 Example D8,8n+6 -- 5.2 Example D6,6n+2 -- 5.3 Example D6,9. -- References -- Ambiguity of Morphisms in a Free Group -- 1 Introduction -- 2 Preliminaries -- 3 Basic Ambiguity -- 4 Unambiguous Injective Morphisms -- 4.1 Main Theorem -- 4.2 Proof Outline -- 5 Patterns with Terminal Symbols -- References -- The Degree of Squares is an Atom -- 1 Introduction -- 2 Preliminaries -- 3 Finite-State Transducers and Degrees -- 4 Characterising Transducts of Spiralling Sequences -- 5 Squares -- References -- Words with the Maximum Number of Abelian Squares -- 1 Introduction -- 2 Notation and Background -- 3 Abelian-square Rich Words -- 3.1 The Thue-Morse Word -- 3.2 Sturmian Words -- 4 Conclusions and Future Work -- References -- Arithmetics on Suffix Arrays of Fibonacci Words -- 1 Introduction -- 2 Related Work -- 3 Preliminaries -- 4 The Suffix Array and Its Inverse -- 5 Burrows-Wheeler Transform -- 6 Outlook -- References -- Prefix-Suffix Square Completion -- 1 Introduction -- 2 Definitions -- 3 Generating Infinite Words -- 4 Finite Words: Algorithms -- 5 Future Work -- References -- Square-Density Increasing Mappings -- 1 Introduction -- 2 Preliminaries -- 3 Fractional-Power Density Increasing Mappings to Expand the Alphabet -- 3.1 Fractional-Power Density Preserving Quaternarizer -- 3.2 Fractional-Power Density Preserving Mappings to Double the Alphabet Size -- 4 Strictly Square-Density Increasing Mappings -- 4.1 Strictly Square-Density Increasing Alphabet Downsizer -- 5 Future Work -- References -- Mechanical Proofs of Properties of the Tribonacci Word -- 1 Introduction -- 2 Tribonacci Representation -- 3 Mechanical Proofs of Properties of the Infinite Tribonacci Word -- 3.1 Repetitions -- 4 Enumeration -- 5 Additional Results -- 5.1 Palindromes -- 5.2 Quasiperiods -- 5.3 Unbordered Factors -- 5.4 Lyndon Words.; 5.5 Critical Exponent -- 6 Abelian Properties -- 7 Things We Could Not Do Yet -- References -- On Arithmetic Progressions in the Generalized Thue-Morse Word -- 1 Introduction -- 2 Preliminaries -- 3 Main Result -- 3.1 Case of d=3n-1 -- 3.2 Case of d=3n-1 -- 4 Conclusion -- References -- A Square Root Map on Sturmian Words -- 1 Introduction -- 2 Notation and Preliminary Results -- 2.1 Optimal Squareful Words -- 2.2 Continued Fractions -- 2.3 Sturmian Words -- 2.4 Powers in Sturmian Words -- 3 The Square Root Map -- 4 One Characterization of Words Satisfying the Square Root Condition -- 5 Characterization by a Word Equation -- 6 A More Detailed Combinatorial Description of the Square Root Map -- References -- Specular Sets -- 1 Introduction -- 2 ; Preliminaries -- 3 Specular Groups -- 4 Specular Sets -- 5 Subgroup Theorems -- References -- On the Tree of Ternary Square-Free Words -- 1 Introduction -- 2 Definitions and Notation -- 3 Letters Fixed by Short Squares -- 4 Long Squares -- 5 Discussion -- References -- Author Index.
• Sommario/riassunto: 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.