139,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Serie: ISTE
- Sprache: Englisch
Formal Languages, Automaton and Numeration Systems presents readers with a review of research related to formal language theory, combinatorics on words or numeration systems, such as Words, DLT (Developments in Language Theory), ICALP, MFCS (Mathematical Foundation of Computer Science), Mons Theoretical Computer Science Days, Numeration, CANT (Combinatorics, Automata and Number Theory).
Combinatorics on words deals with problems that can be stated in a non-commutative monoid, such as subword complexity of finite or infinite words, construction and properties of infinite words, unavoidable regularities or patterns. When considering some numeration systems, any integer can be represented as a finite word over an alphabet of digits. This simple observation leads to the study of the relationship between the arithmetical properties of the integers and the syntactical properties of the corresponding representations. One of the most profound results in this direction is given by the celebrated theorem by Cobham. Surprisingly, a recent extension of this result to complex numbers led to the famous Four Exponentials Conjecture. This is just one example of the fruitful relationship between formal language theory (including the theory of automata) and number theory.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 439
Veröffentlichungsjahr: 2014
Ähnliche
Contents
Foreword
Introduction
1.1. What this book is or is not about
1.2. A few words about what you will find
1.3. How to read this book
1.4. Acknowledgments
1 Words and Sequences from Scratch
1.1. Mathematical background and notation
1.2. Structures, words and languages
1.3. Examples of infinite words
1.4. Bibliographic notes and comments
2 Morphic Words
2.1. Formal definitions
2.2. Parikh vectors and matrices associated with a morphism
2.3. Constant-length morphisms
2.4. Primitive morphisms
2.5. Arbitrary morphisms
2.6. Factor complexity and Sturmian words
2.7. Exercises
2.8. Bibliographic notes and comments
3 More Material on Infinite Words
3.1. Getting rid of erasing morphisms
3.2. Recurrence
3.3. More examples of infinite words
3.4. Factor Graphs and special factors
3.5. From the Thue–Morse word to pattern avoidance
3.6. Other combinatorial complexity measures
3.7. Bibliographic notes and comments
Bibliography
Index
Summary of Volume 2
First published 2014 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.
Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:
ISTE Ltd
27-37 St George’s Road
London SW19 4EU
UK
www.iste.co.uk
John Wiley & Sons, Inc.
111 River Street
Hoboken, NJ 07030
USA
www.wiley.com
© ISTE Ltd 2014
The rights of Michel Rigo to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.
Library of Congress Control Number: 2014945516
British Library Cataloguing-in-Publication Data
A CIP record for this book is available from the British Library
ISBN 978-1-84821-615-0
To Christelle, Aurore and Maxime.
Foreword
The interplay between words (in the most general sense, including symbolic dynamics), computability, algebra and arithmetics has now proved its relevance and fruitfulness. Indeed, the cross-fertilization between formal logic and finite automata (such as that initiated by J.R. Büchi), or between logic and aperiodic substitutive tilings (through Wang–Berger–Robinson works) has paved the way to recent dramatic developments. Let us quote, for example, the characterization of the entropies of multidimensional shifts of finite type as right recursively enumerable numbers, by M. Hochman and T. Meyerovitch, or the transcendence results for the real numbers having a “simple” binary expansion, by B. Adamczewski and Y. Bugeaud.
This book is at the heart of this interplay through its unified exposition of the connections between formal languages, automata and numeration, with a number-theoretic flavor. Moreover, objects here are considered with a perspective that comes from both theoretical computer science and mathematics. Here, theoretical computer science offers topics such as decision problems and recognizability issues, whereas mathematics offers concepts such as discrete dynamical systems. Dynamical systems serve here as a common thread and occur in several forms, such as symbolic forms, or as systems of an arithmetic nature (e.g. the Gauss map of continued fractions) in the framework of numeration and arithmetic dynamics, or else, as cellular automata.
But let us come back to the core of this book, namely words. This book provides a systematic treatment of the concepts that have to do with words (and their combinatorics) in all their forms. Here, words are finite or infinite, they are considered alone or they come in sets (languages or subshifts). They can also be multidimensional. They are most often simple in a way that is well explored here through the review of the numerous existing notions of complexity that allow their classification. They are generated by morphisms (these are substitution rules that replace letters by words), they are accepted by simple machines like automata, they are definable with respect to a logical expression, or else, they code classical dynamical systems of an arithmetic nature, such as interval exchanges or Sturmian codings of circle translations.
Words are, moreover, considered from the two complementary viewpoints of word combinatorics and symbolic dynamics. Combinatorics on words studies the combinatorial properties of sequences of symbols (as an illustration, consider the classical subject of occurrences of powers of factors with example the recently solved Dejean’s conjecture), whereas symbolic dynamical systems are compact sets of infinite words with dynamics provided by the shift, endowed possibly with a measure which contains probabilistic information on these words (e.g. the frequencies of their factors). All these approaches yield different questions, classifications, etc.
But why are words and their study so important? It is because of their representation power: they are a natural way to code elements of an infinite set using a finite amount of symbols. In this context, numeration systems play a specific role. And their treatment in this book is again a perfect illustration of the interconnection between computer science and mathematics. As an example, an arithmetic property of the base of a numeration system, such as being a Pisot number, is revisited from the viewpoint of recognizability, by exploring the way arithmetic properties are reflected in the representation. Similarly, finite automata are known to have strong descriptive power. This is natural if we think of finite automata as representations of finitely generated subgroups of a free group. This has also induced, in the direction of computational and geometric group theory, the fascinating development of automatic groups. But finite automata also serve, of course, as language acceptors, with logic playing an increasing role for the study of regular languages; just think of the recent development of the theory of regular cost functions which is a quantitative extension of the classical notion of regularity. It is in this context that one of the most original chapters of this book (at least in my view) takes place, devoted to the use of formal methods applied to morphic words, through automatic certification of properties expressed as a first-order formula in a suitable system (see Chapter 3, Volume 2 [RIG 14]).
A few words now concerning the “genesis” of this book. I have known Michel for many years and I have seen him develop into an impressive lecturer, famous for his work in popularizing mathematics, in addition to also being a highly recognized expert in his field. When I suggested that he use his teaching experience to write about numeration and automata, he responded enthusiastically. The result is this book written in Michel’s personal style and with his sense of humor. It will serve as a clear and accessible introduction to the field, being a highly valuable tool for teaching and making the subject accessible to a wide audience, thanks to its numerous exercises, self-contained chapters and very large number of examples. But, by being connected to the most recent research developments, it will also serve as a reference book to experts in the area who will still learn new things. I am surprised both by the extent of its coverage and by the impressive variety of examples issued from the various viewpoints. I hope you enjoy reading it as much as I did.
Valérie Berthé
July 2014
Introduction
This book, comprised of two volumes, is a somewhat extended version of lectures basically dedicated to combinatorics on words and numeration systems that I am giving at the University of Liège. The course is usually (but not necessarily) followed by students interested in discrete mathematics or theoretical computer science. The chosen level of abstraction should allow undergraduate students to study the exposed topics.
1.1. What this book is or is not about
In the long process of writing this book, I have expanded my initial notes with many examples and many extra concepts to acquire a consistent overview of the field. Nevertheless, this book is not intended to serve as an encyclopedic reference.
I have picked some of my favorite topics in the area and I have also decided to shorten the presentation of some items (not because there are less interesting but choices had to be made to keep this book reasonably short). Indeed, the book most probably reflects what I myself prefer: I am always more interested in the combinatorics and the underlying discrete structures arising from a problem.
When preparing this book, I chose to present a fairly large variety of basic notions and important tools and results. Sometimes, I only give an overview of a subject and proofs are, therefore, omitted. For the reader wanting to study a specific topic further, many pointers to the relevant bibliography are given and each chapter ends with notes and comments. Indeed, the main goal of this book is to give quick access to actual research topics at the intersection between automata and formal language theory, number theory and combinatorics on words.
1.2. A few words about what you will find
The notion of a word, i.e. a (finite or infinite) sequence of symbols belonging to a finite set, is central throughout this book. It has connections with many branches of mathematics and computer science: number theory, combinatorics, formal language theory, mathematical logic, symbolic dynamics, coding theory, computational complexity, discrete geometry, stringology, etc.
Combinatorics on words. We can be interested in the combinatorial properties of finite or infinite sequences of symbols over a finite alphabet: what the possible arrangements are, how many such configurations can be achieved and so on. As a trivial example, over a binary alphabet any word of a length of at least 4 contains a repeated factor of the kind uu (try to prove it). Therefore, we can look at patterns that are unavoidable in sufficiently long sequences or count the number of patterns or configurations that may appear in a particular context. These are some of the general questions that will be considered in this Volume. In particular, we will concentrate on infinite words that can be obtained by a simple procedure consisting of the iteration of a morphism over a free monoid. We will mostly deal with a large class of self-similar words: the so-called morphic words and, in particular, and with automatic sequences that are generated by a constant-length morphism.
Formal language theory. A language is merely a set of words. In this book, we will mostly encounter languages of finite words. One exception is a short incursion into symbolic dynamical systems with the language of the β-expansions of the real numbers in the interval [0, 1). Chomsky’s hierarchy introduced in the theory of formal languages provides a classification depending on the machine needed to recognize an infinite language of finite words. From a computational perspective, the simplest languages are the regular languages. They are accepted (or recognized) by finite automata, and described by regular expressions. Chapter 1, Volume 2 is a short chapter presenting the main properties of these languages. We will constantly see connections existing between regular languages, automatic sequences and numeration systems. For instance, quite often we associate a finite automaton with a morphism.
Number theory. A finite word can also be used to represent an integer in a given numeration system (e.g. integer base expansions and many other non-standard systems are discussed in depth in several chapters of this book). To quote A. Fraenkel: “There are many ways of representing an integer uniquely!” [FRA 85]. Similarly, an infinite word can represent a real number or the characteristic sequence of a set of integers. With that respect, a natural question is to study links existing between arithmetical properties of numbers (or sets of numbers) and syntactical properties of their expansions. Chapter 2, Volume 2 is dedicated to numeration systems with a particular emphasis on words representing numbers. Indeed, the chosen numeration system has a strong influence on the syntactical properties of the corresponding representations. A cornerstone is the notion of a recognizable set of numbers whose elements, when represented within a given numeration system, are recognized by a finite automaton.
Formal methods applied to infinite words and sets of numbers. In Chapter 3 of Volume 2, I describe a recent trend in combinatorics on words. Due to automata theory and Büchi’s theorem, we will see how formal methods enter the frame regarding decision problems, or automatic theorem-proving, relevant in combinatorics on words. If a property about some infinite words can be described by a well-written logical formula, then this property can be tested automatically. Such a procedure holds for a large class of infinite words generated by iterated morphisms (for automatic sequences and those stemming from Pisot numeration systems as presented in this book). The expressiveness of Presburger arithmetic (with an extra predicate) provides an interesting alternative to dealing with a sufficiently large class of problems about infinite morphic words. We can imagine automated certificates for several families of combinatorial properties. But the price to pay is that we would have to deal with fairly large automata. It is a field of research where combinatorists and computer scientists can work together fruitfully: on the one hand, it is well-known that, in the worst-case, the obtained decision procedures can be super-exponential, but on the other hand, the considered problems about words seem to be of relatively small complexity.
1.3. How to read this book
The goal is that, after reading this book (or at least parts of this book), the reader should be able to fruitfully attend a conference or a seminar in the field. I hope that the many examples presented along the text will help the reader to get some feeling about the presented topics even though we are not going too far in the technical aspects of the proofs. Also, prerequisites are minimal. We will not explore topics requiring measure theory or advanced linear algebra (we have avoided results related to Jordan normal form of matrices) or non-elementary number theory. Two sections are devoted to results in algebraic number theory and formal series. Sections 1.1.2 and 1.2.2 serve as references that the reader may consult when needed. Sections 3.1 and 3.2 of Volume 2 give a self-contained presentation of the concepts of mathematical logic needed in this book. Those rigorous and technical sections should not discourage the reader to pursue his/her study. Most of the material can be accessed without much background.
My initial aim was to quickly get to the point but it seems that the stories I wanted to tell were indeed quite longer than I initially thought. I have to confess that writing this book was a quite unexpected adventure (I was perpetually trying to meet the deadlines and also dealing with my other duties at the University and at home).
There are several paths that the reader can follow through this book. Some are quite long, some are shorter.
– For a basic introduction, I propose reading parts of Chapter 1 (skipping the reference sections), Chapter 2 up to and including section 2.4. If the reader already has some knowledge about automata, then we can conclude with Chapter 3, Volume 2, concentrating on results about integer base systems.
– For a one-semester course in combinatorics on words, I propose a reading of the first three chapters, not sacrificing the rigorous presentation of section 1.2.1.
– For a numeration system oriented reading, again organized over one semester: browse through the first chapter (with a careful reading of the examples related to numeration systems), then go to section 2.3 and conclude with the last two chapters of Volume 2.
– For a course oriented toward interaction between automata, logic and numeration systems, we can focus on Chapters 1 and 3 of Volume 2.
About other sources treating similar subjects, an excellent companion for this book is definitely Automatic Sequences: Theory, Applications, Generalizations [ALL 03a] written by Allouche and Shallit. I do hope that the two books can be read independently and can benefit from each other. There is also a non-zero intersection with several chapters of the Lothaire’s book Algebraic Combinatorics on Words (namely those about Sturmian words written by Berstel and Séébold and the one on numeration systems written by Frougny) [LOT 02]. Some chapters of the volume Combinatorics, Automata and Number Theory [BER 10] as well as [PYT 02] can also serve as a follow up for the present book. In particular, Cassaigne and Nicolas’s chapter on factor complexity is a natural continuation for our Chapter 2. I should finish by mentioning two papers that were very influential in my work: [BRU 94] and [BRU 95]. With this book, I hope that the reader would learn as much material as found in these two papers.
Tags of bibliographic entries are based on the first three letters of the last name of the first author and then the year of publication. In the bibliography, entries are sorted in alphabetical order using these tags.
I intend to make a page:
for errata and comments about this book.
1.4. Acknowledgments
I would like to express my gratitude to Valérie Berthé for her constant and enthusiastic support, for the many projects we run together and finally, for her valuable comments on a draft of this book.
Several researchers have spent some precious time reading a first draft of this book, their careful reading, their feedback and expert comments were very useful and valuable: Anna Frid, Julien Leroy, Aline Parreau, Narad Rampersad, Eric Rowland, Aleksi Saarela and Jeffrey Shallit. They proposed many clever improvements of the text. I warmly thank them all. I would like to give a special thank to Véronique Bruyère for comments on the last chapter of Volume 2.
I also sincerely thank Jean-Paul Allouche, Émilie Charlier, Fabien Durand and Victor Marsault for their feedback.
Even though he was not directly involved in the writing process of this book, the first half of the book has greatly benefited from the many discussions I had with Pavel Salimov when he was a postdoctoral fellow in Liège. Naturally, all the discussions and interactions I could have had along the years with students, colleagues and researchers worldwide had some great influence on me (but such a list would be too long) and I thank them all.
Michel RIGO
July 2014
1
Words and Sequences from Scratch
For the development of logical sciences it will be important, without consideration for possible applications, to find large domains for speculations about difficult problems. [...]
we present some investigations in the theory of sequences of symbols, a theory which has some connections with number theory.
Axel Thue [THU 12]
In this first chapter we introduce the basic objects that are encountered in the different parts of this book. The main aim is to give quick access (but without sacrificing a rigorous introduction) to some major notions arising in combinatorics on words. These are illustrated by many examples. The supporting goal is that, after reading this book, the reader should be able to fruitfully attend a research conference or seminar in the field. We do not present a proof of every stated result. We have made some choices depending on the notions and constructions that we want to emphasize.
Notions arising from automata theory are kept to a minimum (but we cannot avoid them completely when presenting words generated by constant-length morphisms). A self-contained presentation of finite automata and some of their properties is given in Chapter 1, Volume 2.
Here, we also present notions arising in (symbolic) dynamical systems, because the exchanges between these two areas of research should not be neglected and are profitable for both communities. Even though they are important, measure-theoretic notions and results coming from ergodic theory will not be presented in this book.
After this chapter, the reader will have been introduced to words, factor complexity, the formalism of symbolic dynamical systems, and Sturmian words. In the second chapter, we will present important classes of infinite words: k-automatic words and morphic words, with an emphasis on Perron–Frobenius theory. The chapters end with bibliographic notes giving pointers to further readings on the topics merely approached here. In the third chapter, we have put extra material on words: other measures of complexity of sequences, avoidance, recurrence and some tools, e.g. Rauzy graphs, to analyze words.
1.1. Mathematical background and notation
For instance, >0 can be written \{0} or ≥1. Let i, j ∈ with i ≤ j. We let denote the set of integers {i, i + 1 , ..., j}.
1.1.1. About asymptotics
Let us recall here notation about asymptotics. Let (xn)n≥0 be a sequence of real numbers (a sequence is a map defined over ). Recall that the limit superior of (xn) n≥0 is defined as
If the sequence is unbounded, this quantity could be infinite. Similarly, we can define the limit inferior of (xn) n≥0. We can also find the notation
Let f, g : be two functions. The definitions given below can also be applied to functions defined on another domain such as >a, or to sequences defined over . We implicitly assume that the following notions are defined for x → + ∞. We write f ∈ (g), if there exist two constants x0 and C > 0 such that, for all x ≥ x0,
If g belongs to (f) ∩ Ω(f), i.e. there exist constants x0, C1, C2with C1, C2 > 0 such that, for all x ≥ x0,
Figure 1.1.The functionsx2 + sin(6x), x2| sin(4x)|, 4x2/5 and 6x2/5
1.1.2. Algebraic number theory
DEFINITION 1.1.–Let be a field. The ring of polynomials with coefficients in is denoted by [X]. Since is a field, the ring [X] is a Euclidean domain and thus a principal ideal domain.
Let be an extension field of (if you prefer, we can consider as a subfield of the field ). An element α ∈ is algebraic over if it is a root of a non-zero polynomial in [X]. If α ∈ is not algebraic over , then it is said to be transcendental over .
Let α ∈ be algebraic over . Since the ring [X] is a principal ideal domain, the ideal
is principal. Thus there exists a unique monic (i.e. the leading coefficient is 1) polynomial Mα ∈ [X] generating the ideal ,
[1.1]
Usually, we will restrict ourselves to the fields of rational numbers and complex numbers. We say that a complex number α is algebraic if it is algebraic over . So, in what follows, it should be understood that we are considering the ideal (α) and Mα belongs to [X]. Rational numbers are trivially algebraic numbers.
DEFINITION 1.2.– A complex number α is an algebraic integer if it satisfies
where an–1, … ,a0 belong to . We can also say that α is integral over . Clearly, algebraic integers are algebraic numbers. It is well known that the set of algebraic integers is an integral domain [ALA 04]. Note that if α ∈ \ , then α is an algebraic number but it is not an algebraic integer. We will make use of these latter two observations in the proof of proposition 1.4.
For an example of algebraic integers, consider a square matrix M ∈ t×t. The characteristic polynomial of M belongs to [X]. Hence, the eigenvalues of M are algebraic integers. Another important class of algebraic numbers that we will deal with, are the Pisot numbers. A real number α > 1 is a Pisot number (also called Pisot–Vijayaraghavan number) if it is an algebraic integer whose conjugates have modulus less than one [PIS 46].
By definition, an algebraic number has a minimal polynomial in [X]. We will show that algebraic integers have minimal polynomials in [X].
PROPOSITION 1.3.– The conjugates of an algebraic integer are also algebraic integers.
■
PROPOSITION 1.4.– Let α be an algebraic integer. The minimal polynomial of α belongs to [X].
By Viète’s formulas relating the coefficients of a polynomial to sums and products of its roots, that is by expanding the above product, we get
From the previous proposition, we know that α1, α2,…, αn are algebraic integers. Since the set of algebraic integers is a ring, the coefficients of Mα
are also algebraic integers but they are also rational because Mα ∈ [X]. The only rational numbers that are algebraic integers are the integers. Hence, the coefficients of Mα are integers.
■
Let α be a complex number. We let (α) denote the smallest subfield of containing both and α. Recall that (X) is the field of rational functions of the form P/Q where P, Q belong to [X] and Q is non-zero, i.e. it is the field of fractions of [X]. So the notation (α) is meaningful:
■
As an example, a fundamental property of Pisot numbers is as follows:
If α is a Pisot number and if λ is an algebraic number belonging to (α), then the sequence of distances of λ times powers of α to the nearest integer tends to zero as n tends to infinity. In his original paper, Pisot gives necessary and sufficient conditions for such a result to hold.
In this book, the reader will be introduced to sequences taking values in a finite set. To define operations on such a set of sequences (like we can do in an equivalent way with formal series, see section 1.2.2), it is meaningful to consider sequences taking values in a finite field. Operations defined on the field lead to operations on the set of sequences such as pointwise addition, multiplication by an element in the field or the so-called Cauchy product of two sequences.
Let p be a prime. We get p by simply considering the ring /(p) of integers modulo p (which turns out to be a field). Let n ≥ 2. To build a copy of pn, we can proceed as follows. Take an irreducible polynomial P of degree n over p (it can be shown that such a polynomial always exists). The quotient ring
contains the equivalence classes Q + 〈P〉 where Q is polynomial of degree less than n. Hence this ring contains exactly pn distinct classes (or residue classes modulo P). Since the polynomial P is irreducible, we can prove the following. The ideal 〈P〉 is maximal (with respect to inclusion among all proper ideals) and thus the quotient ring turns out to be a field.
1.2. Structures, words and languages
In this section, in comparison to rings and fields, we consider some quite elementary algebraic structures.
In this book, we will be dealing with words. So be aware of the fact that the concatenation product, given in definition 1.10, is not commutative (except over a one-letter alphabet).
EXAMPLE 1.8.– Every group is a monoid. Hence (, +), ( \ {0}, ·) and (, +) are monoids. But (, +) is a monoid which is not a group.
Let A, S be sets. Usually in this book, a capital letter such as A or B will denote an alphabet, which is simply a finite set. The elements of an alphabet are called letters or symbols. A sequence over A indexed by S is an element of AS, that is a map from S to A. If S is a finite set of cardinality n > 0, then w ∈ AS is said to be a finite word6 of lengthn > 0 over A. In particular, to order the set S we assume that . The length of w is denoted by |w|. We usually use the notation wi instead of w(i) and a word w is generally represented by its successive letters:
If S is empty, the corresponding sequence is said to be the empty word denoted by . The set of finite words over the alphabet A (including the empty word) is denoted by A*. The set of words of length n over A is denoted by An. This notation is consistent with the fact that n can be identified with the set in the Zermelo-Fraenkel theory for the natural numbers.
REMARK 1.9.– We have adopted the convention that the index of the first letter of a word is 0. Of course, we could decide to start indexing with 1. Nevertheless, there are several reasons to start with 0. In the context of automatic sequences (see section 2.3), it is meaningful to start with 0. Also, when a word w0w1 … wn–1 is the representation of an integer (e.g. base-b expansion), then the corresponding value is
It is convenient that the indices, as well as the exponents of the base b occurring in the above formula, are both between 0 and n – 1.
We will use alphabets of integers such as {0, 1}, {1, 2, 3} or alphabets of letters such as {a, b} or {a, b, c}. In the latter case, we use a typewriter font for a specific letter in the alphabet. Whenever we use a generic symbol from a given alphabet, we will make use of a notation like a ∈ A with the classical italic font for mathematical formulas.
Let us now introduce orders on words. The sets A* and A can be ordered as follows.
Observe that over a unary (i.e. single letter) alphabet, the two orderings over {a}* coincide but if the cardinality of the alphabet A is at least 2, then the radix order is a well order (i.e. every non-empty subset of A* has a least element for this order) but the lexicographic order is not a well order. For instance, the set of words {anb | n ≥ 0} does not have a least element for the lexicographic order (assuming a < b).
EXAMPLE 1.13 (Characteristic sequence of the primes).– We let denote the set of primes. The characteristic sequence of is the infinite word
EXAMPLE 1.15 (Pseudo-random sequence).– Let p be a (large) prime. Consider the following simple method to build a “pseudo-random” sequence over {0, 1}. Let γ, x0 ∈ /(p). Define, for all n ≥ 0, the two sequences
1.2.1. Distance and topology
Even though it is not difficult to figure out what a sequence of finite words converging to some infinite limit word like 0, 01, 010, 0101, 01010, … converging to (01)ω is, this concept should be clearly introduced. Thus we define a distance turning A into a (complete) ultrametric9 space for which the notion of convergence is usual.
DEFINITION 1.16.– A set X equipped with a map d : X × X → ≥0 satisfying, for all x, y, z ∈ X
is a metric space and d is a distance on X.
DEFINITION 1.17.– Let w, x be two distinct infinite words in A. We let Λ(w, x) denote the longest common prefix of w and x and we define a map d : A × A → ≥0 by
This inequality is readily verified when comparing |Λ(w, x)|, |Λ(w, y)| and |Λ(y, x)|.
Note that we obtain an equivalent distance if we replace 2 with any real number r > 1.
The reader familiar with basic notions encountered in any course on analysis or topology will have no problem with the next paragraph. We will recall standard notions arising in metric spaces or topological spaces. For the sake of completeness, recall that a topological space is a set X together with a collection of subsets of X, called open sets and satisfying the following three properties:
The set 2X is called a topology on X. If X \ S is open, then S is a closed set. Having a distance at hand, we can easily consider topological notions such as balls, converging sequences of elements in A or closure of a subset of A.
Let w be an infinite word over A and let r > 0 be a real number. An (open) ball centered at w of radius r is the set . In any ultrametric space (thus in particular for A), the following statement holds.
LEMMA 1.19.– Let and be two open balls of A. We have that is non-empty if and only if or .
Observe that there exists a finite prefix u of w such that
For instance, A is the disjoint union of the two balls aA and bA. Moreover, every set of the form uA, for some finite word u ∈ A*, is itself partitioned into uaA and ubA. These balls are examples of what is called a cylinder set.
Figure 1.2.A representation of possible partitions of {a, b}
DEFINITION 1.20.– Let i ≥ 0. Let u be a finite word. The set of infinite words where u occurs at position i,
is a cylinder set. In this definition, we have only conditions on the first i + |u| letters of an infinite word. Hence such a cylinder is a finite union of (open) balls,
For the same reasons and since A is finite, the complement of a cylinder set is also a finite union of (open) balls
Therefore a cylinder set is both open and closed. We say that it is a clopen set.
It is standard that a distance induces a topology, i.e. a collection of open sets. A subset SA is open if, for every x in S, there exists r > 0 such that is included in S. Hence A can be seen as a topological space where the open balls form a base for the topology, i.e. every open set is a union of open balls. As an example, the set
containing all the infinite word having a prefix with an even number of a’s followed by one b is open.
DEFINITION 1.21. –Let (wn)n≥0 be a sequence of infinite words over the alphabet A. This sequence converges to the word z ∈ A if d(wn, z) → 0 whenever n → +∞. Equivalently, for all r > 0, there exists N such that, for all n ≥ N, wn belongs to . Otherwise stated, for all , there exists N such that, for all n > N, wn and z share a common prefix of length at least We say that z is the limit of the converging sequence (wn)n≥0.
In Chapter 2, we will generalize this notion of convergence to a sequence of finite words converging to some infinite words. The idea is basically to extend finite words to infinite words and use the definition we have just introduced. But here, let us continue to deal with infinite words only.
We now present an alternative way to introduce a topology on A. It turns out that this definition is equivalent to the one we have just developed. It is interesting to know both ways. Indeed, picking a mathematical paper in the literature at random, the author of such an article presents his/her results the way he/she likes. So we should definitely be confident knowing both approaches.
First start with the finite alphabet A equipped with the discrete topology: every singleton is an open set and thus any subset of A is also open. The set A can be seen as the Cartesian product of countably many copies of A. We recall some minimal material on product topology. Let (Xi)i≥0 be a sequence of topological spaces (each space carries its own topology). Consider the Cartesian product This set can be equipped with a natural topology, called the product topology, where the open sets are the (finite or infinite) unions of sets of the kind
is a closed set containing all the words having only b’s or c’s in even positions and, a’s or c’s in odd positions. Finally, observe that O cannot be obtained as a finite union of balls (or cylinder sets). Assume to the contrary that O is a finite union of balls. Such a condition would imply that there exists a constant such that every word in O is characterized by its prefix of length . But there are words in O such as with no b in odd positions and whose first symbol a occurs in an even position larger than .
This second description in terms of Cartesian product has the advantage that we can make use of an important theorem of Tychonoff: any product of compact spaces is compact [WIL 04]. Recall that a topological space X is compact if from every covering of X with open sets, we can extract a finite covering of X.
Corollary 1.23.– Let A be a finite alphabet. The space A is compact.
Since A is a metric space, compactness of A can be shown to be equivalent to the following fact (sometimes called sequential compactness). For every sequence (wn)n≥0, there exists a converging subsequence (wk(n))n≥0, for some increasing map k : → . Many authors10 refer to this fact of extracting a convergent subsequence as a “compactness argument”.
REMARK 1.24.– Instead of invoking this compactness argument, we could use a variation of the so-called lemma of König (usually expressed in terms of graphs or trees with infinitely many vertices but all having finite degree). Let (wn)n≥0 be a sequence of infinite words over a finite alphabet A. Since A is finite, infinitely many words start with the same first letter a0. We set
DEFINITION 1.25.– Let S be a subset of A. The (topological) closure of S denoted by is defined as follows. A point w ∈ A belongs to if, for every r > 0, we have
REMARK 1.26.– Obviously, the closure of a set is a closed subset. It is well-known that closed subsets of a compact space are compact. Hence from every sequence of elements in we can extract a converging subsequence and contains the limit points of the converging sequences of elements in S.
EXERCISE 1.2.2.– The idea of this exercise is to work out the details of the proof of lemma 1.19. Let be a ball in A, with r < 1. Prove that if the infinite word y belongs to , then it is the center of this ball, i.e. Hence, if two balls and have a non-empty intersection, then or .
EXERCISE 1.2.3.– Prove that, in any ultrametric space, all “triangles” are isosceles.
EXERCISE 1.2.4.– Recall that a sequence (xn)n≥0 in a metric space X endowed with a distance d is a Cauchy sequence if for all , there exists N such that, for all p, q > N, . So in particular, every converging sequence is a Cauchy sequence. Prove that the converse holds in A for the ultrametric distance that we have introduced: every Cauchy sequence of infinite words converges. We say that A is complete.
1.2.2. Formal series
Even though they are a powerful tool and generalize the notion of formal language by adding multiplicities in a convenient algebraic structure, formal power series appear only rarely in this book. This section can be skipped on a first reading. We provide only the main definitions.
DEFINITION 1.27. – A semiring is a set equipped with two operations + and · such that
Compared with the definition of a ring, we see that what is missing is that (, +) is merely a monoid and not a group. For instance, we will consider the semiring of natural numbers or the 2-element Boolean semiring . Of course, every ring or field is a semiring.
Let M be a monoid and be a semiring. A formal (power) series over M with coefficients in is a map from M to ,
For a general reference, see, for instance, [BER 11]. In this context of formal series, the convention is to write (s, m) instead of s(m). The set of such series is denoted by Let s,t be formal series is The sum of s and t is defined by
With this operation, is a monoid. We can also define (left and right) multiplication by an element of . For all a ∈ ,, we set
