Sequences, Groups, and Number Theory

Description

This collaborative book presents recent trends on the study of sequences, including combinatorics on words and symbolic dynamics, and new interdisciplinary links to group theory and number theory. Other chapters branch out from those areas into subfields of theoretical computer science, such as complexity theory and theory of automata. The book is built around four general themes: number theory and sequences, word combinatorics, normal numbers, and group theory. Those topics are rounded out by investigations into automatic and regular sequences, tilings and theory of computation, discrete dynamical systems, ergodic theory, numeration systems, automaton semigroups, and amenable groups. This volume is intended for use by graduate students or research mathematicians, as well as computer scientists who are working in automata theory and formal language theory. With its organization around unified themes, it would also be appropriate as a supplemental text for graduate level courses. Front Matter ....Pages i-xxvi General Framework (Valérie Berthé, Michel Rigo)....Pages 1-36 Number Theoretic Aspects of Regular Sequences (Michael Coons, Lukas Spiegelhofer)....Pages 37-87 First-Order Logic and Numeration Systems (Émilie Charlier)....Pages 89-141 Some Applications of Algebra to Automatic Sequences (Jason Bell)....Pages 143-175 Avoiding or Limiting Regularities in Words (Pascal Ochem, Michaël Rao, Matthieu Rosenfeld)....Pages 177-212 Coloring Problems for Infinite Words (Caïus Wojcik, Luca Q. Zamboni)....Pages 213-231 Normal Numbers and Computer Science (Verónica Becher, Olivier Carton)....Pages 233-269 Normal Numbers and Symbolic Dynamics (Manfred Madritsch)....Pages 271-329 About the Domino Problem for Subshifts on Groups (Nathalie Aubrun, Sebastián Barbieri, Emmanuel Jeandel)....Pages 331-389 Automaton (Semi)groups: Wang Tilings and Schreier Tries (Ines Klimann, Matthieu Picantin)....Pages 391-431 Amenability of Groups and G-Sets (Laurent Bartholdi)....Pages 433-544 Back Matter ....Pages 545-576