Combinatorics, Automata and Number Theory
Valérie Berthé, Michel Rigo
Cambridge University Press, Aug 12, 2010 - Mathematics - 615 pages
This collaborative volume presents recent trends arising from the fruitful interaction between the themes of combinatorics on words, automata and formal language theory, and number theory. Presenting several important tools and concepts, the authors also reveal some of the exciting and important relationships that exist between these different fields. Topics include numeration systems, word complexity function, morphic words, Rauzy tilings and substitutive dynamical systems, Bratelli diagrams, frequencies and ergodicity, Diophantine approximation and transcendence, asymptotic properties of digital functions, decidability issues for D0L systems, matrix products and joint spectral radius. Topics are presented in a way that links them to the three main themes, but also extends them to dynamical systems and ergodic theory, fractals, tilings and spectral properties of matrices. Graduate students, research mathematicians and computer scientists working in combinatorics, theory of computation, number theory, symbolic dynamics, fractals, tilings and stringology will find much of interest in this book.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Number representation and ﬁnite automata
Abstract numeration systems
Substitutions Rauzy fractals and tilings
Combinatorics on Bratteli diagrams and dynamical systems
Inﬁnite words with uniform frequencies
Transcendence and Diophantine approximation
Other editions - View all
algebraic alphabet assume automaton balanced pair bispecial factors bounded Chapter clopen set coincidence condition combinatorial complexity function compute consider continued fraction converges Corollary deﬁned Deﬁnition denote diﬀerent digits dynamical system eigenvalue element endomorphism eventually periodic Example Exercise exists expansion Fibonacci Fibonacci word ﬁnite ﬁnite automata ﬁnite word ﬁrst given Hence implies infinite inﬁnite word invariant measures joint spectral radius label Lemma letter linear recurrence minimal morphic word morphism multiple tiling non-empty normalisation numeration system overlap coincidence Pisot irreducible substitution Pisot number polynomial positive integer preﬁx Proof Let Proposition prove purely morphic rational Rauzy real number regular language representation result S-recognisable satisﬁes satisfying Section sequence set of matrices spectral radius Sturmian words subset subshift substitutive words symbolic dynamical tiling property topological transducer uniform frequencies uniformly recurrent uniquely ergodic unit Pisot irreducible words of length