# Automatic Sequences: Theory, Applications, Generalizations by Jean-Paul Allouche

By Jean-Paul Allouche

Combining recommendations of arithmetic and machine technology, this publication is set the sequences of symbols that may be generated by way of easy types of computation known as ''finite automata''. appropriate for graduate scholars or complex undergraduates, it begins from effortless rules and develops the fundamental thought. The examine then progresses to teach how those rules might be utilized to unravel difficulties in quantity thought and physics.

Best number theory books

The Atiyah-Patodi-Singer Index Theorem

In accordance with the lecture notes of a graduate direction given at MIT, this refined therapy ends up in a number of present study issues and should unquestionably function a advisor to additional reviews.

Zero to Lazy Eight: The Romance Numbers

Did you ever ask yourself why a sew in time saves 9 and never, say, 4, or why the quantity seven is taken into account the luckiest, or what percentage the note googol refers to? good, the Humez brothers, besides Joseph Maguire, have responded all of those questions and extra. In "Zero to Lazy Eight", they take us on a wacky and enlightening journey up the linguistic quantity scale from 0 to 13 and again when it comes to infinity, displaying us simply what numbers can let us know approximately our culture's previous, current, and destiny.

Extra info for Automatic Sequences: Theory, Applications, Generalizations

Sample text

Show that any integer linear combination of the wi is ultimately periodic. 9. Let x, y ∈ ∗ be words. Show that there exists z ∈ ∗ such that x 2 y 2 = z 2 if and only if x y = yx. 10. In the Lyndon–Sch¨utzenberger theorems, we proved a necessary and sufﬁcient condition for x y = yx and x y = yz. Find similar necessary and sufﬁcient conditions for the following to hold: (a) x y = y R x; (b) x y = y R z. 11. Let x, y, z, w be words. Find necessary and sufﬁcient conditions for the following two equations to hold simultaneously: x y = zw and yx = wz.

The following corollary completely characterizes the binary sequences that are ﬁxed points of non-identity morphisms. 9 An inﬁnite overlap-free binary word is a ﬁxed point of a nonidentity morphism if and only if it is equal to t, the Thue–Morse word, or its complement t. Proof. Let h be a non-identity morphism on the alphabet 2 . Let x be a ﬁxed point of h that is overlap-free. 8 above, we see that the morphism h, mapping an overlap-free inﬁnite word to an overlap-free inﬁnite word, must be of the form µk or E ◦ µk , for some k ≥ 0.

Since h is non-identity, h = µk for some k ≥ 1. But t and t are the only ﬁxed points of µk , and the corollary is proved. 8 Additional Topics on Repetitions There are many other topics dealing with repetitions in words. We content ourselves with a brief survey. We can deﬁne the concept of fractional power. We say a (ﬁnite or inﬁnite) word w contains an α-power (real α > 1) if w has a subword of the form x α x where x is a preﬁx of x and |x α x | ≥ α|x|. For example, the word 2301 01234567 01234567 0123 310 has a 52 -power.