Automatic Sequences: Theory, Applications, Generalizations

ISBN-13: 9780521823326 / Angielski / Twarda / 2003 / 588 str.

Jean-Paul Allouche; Jeffrey Shallit

Opis

Combining concepts of mathematics and computer science, this book is about the sequences of symbols that can be generated by simple models of computation called "finite automata." Suitable for graduate students or advanced undergraduates, it starts from elementary principles and develops the basic theory. The study then progresses to show how these ideas can be applied to solve problems in number theory and physics.

Recenzje

'Allouche and Shallit's books presents an introduction to the fascinating subject of automatic sequences. This is the first book that systematically develops the theory of these sequences.' Zentralblatt MATH

Spis treści

Preface; 1. Stringology; 2. Number theory and algebra; 3. Numeration systems; 4. Finite automata and other models of computation; 5. Automatic sequences; 6. Uniform morphisms and automatic sequences; 7. Morphic sequences; 8. Frequency of letters; 9. Characteristic words; 10. Subwords; 11. Cobham's theorem; 12. Formal power series; 13. Automatic real numbers; 14. Multidimensional automatic sequences; 15. Automaticity; 16. k-regular sequences; 17. Physics; Appendix. Hints, references and solutions for selected exercises; Bibliography; Index.