Formal Languages, Automata and Numeration Systems 1

Introduction to Combinatorics on Words

Michel Rigo

• Publisher: Wiley-ISTE
• Year: 2014
• ISBN:
  9781119008224
• Edition: 1
• Topic: Computer Science
• Subtopic: Systems Architecture
• Index: Computer Science

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.

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

We start with some basic notation used throughout this book, and we finish this first section with a recap of some facts coming from algebraic number theory. We assume the reader to be familiar with usual basic set operations such as union, intersection or set difference: difference: ∪, ∩ or \. Sets of numbers are of particular interest. The set of non-negative integers (respectively integers, rational numbers, real numbers, complex numbers) is

(respectively

,

,

,

). Let a be a real number and

= ,

,

,

or

. We set

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}.

We also assume the reader to be familiar with the most common algebraic structu...

Table of contents

• Cover
• Contents
• Title Page
• Copyright
• Foreword
• Introduction
• 1 Words and Sequences from Scratch
• 2 Morphic Words
• 3 More Material on Infinite Words
• Bibliography
• Index
• Volume 2 - Contents
• Volume 2 - Index