Formal Languages, Automata and Numeration Systems 2 E-Book

Michel Rigo

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: ISTE
• Sprache: Englisch

Seitenzahl: 337

Veröffentlichungsjahr: 2014

Beschreibung

The interplay between words, computability, algebra and arithmetic 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 combinatorics on words and number theory has paved the way to recent dramatic developments, for example, 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 a unified exposition. Objects are considered with a perspective that comes both from theoretical computer science and mathematics. Theoretical computer science offers here topics such as decision problems and recognizability issues, whereas mathematics offers concepts such as discrete dynamical systems.

The main goal is to give a quick access, for students and researchers in mathematics or computer science, to actual research topics at the intersection between automata and formal language theory, number theory and combinatorics on words.

The second of two volumes on this subject, this book covers regular languages, numeration systems, formal methods applied to decidability issues about infinite words and sets of numbers.

Leseprobe

To Christelle, Aurore and Maxime.

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 2014The 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: 2014945517

British Library Cataloguing-in-Publication DataA CIP record for this book is available from the British LibraryISBN 978-1-84821-788-1

Contents

Foreword

Introduction

1 Crash Course on Regular Languages

1.1. Automata and regular languages

1.2. Adjacency matrix

1.3. Multidimensional alphabet

1.4. Two pumping lemmas

1.5. The minimal automaton

1.6. Some operations preserving regularity

1.7. Links with automatic sequences and recognizable sets

1.8. Polynomial regular languages

1.9. Bibliographic notes and comments

2 A Range of Numeration Systems

2.1. Substitutive systems

2.2. Abstract numeration systems

2.3. Positional numeration systems

2.4. Pisot numeration systems

2.5. Back to β-expansions

2.6. Miscellaneous systems

2.7. Bibliographical notes and comments

3 Logical Framework and Decidability Issues

3.1. A glimpse at mathematical logic

3.2. Decision problems and decidability

3.3. Quantifier elimination in Presburger arithmetic

3.4. Büchi’s theorem

3.5. Some applications

3.6. Bibliographic notes and comments

4 List of Sequences

Bibliography

Index

Summary of Volume 1

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

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.

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

I.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 Volume 1, [RIG 14]. 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, 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, 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 this Volume, 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.

I.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 of Volume 1 serve as references that the reader may consult when needed. Sections 3.1 and 3.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, Volume 1 (skipping the reference sections), Chapter 2, again Volume 1, up to and including section 2.4. If the reader already has some knowledge about automata, then we can conclude with Chapter 3 of this volume, concentrating on results about integer base systems.

– For a one-semester course in combinatorics on words, I propose a reading of Volume 1, not sacrificing the rigorous presentation of section 1.2.1, Volume 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, of Volume 1, and conclude with the last two chapters of this volume.

– For a course oriented toward interaction between automata, logic and numeration systems, we can focus on Chapters 1 and 3 of this volume.

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, Volume 1. 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:

www.discmath.ulg.ac.be/flans/

for errata and comments about this book.

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

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

Crash Course on Regular Languages

The theory of finite automata has preserved from its origins a great diversity of aspects. From one point of view, it is a branch of mathematics connected with the algebraic theory of semigroups and associative algebras. From another point of view, it is a branch of algorithm design concerned with string manipulation and sequence processing. It is perhaps this diversity that has enriched the field to make it presently one with both interesting applications and significant mathematical problems.

Dominique Perrin [PER 90]

This chapter is intended to be short. Automata theory and formal language theory have been developed for more than 50 years. There are many textbooks devoted to these theories (and we can easily find series of exercises). To cite just a few (all these books cover in particular what is nowadays considered as classical material): [HOP 79] or [SUD 06] where the focus is oriented toward the computational models and the corresponding algorithms, the comprehensive [SAK 09] where a wider perspective, a more general algebraic framework and emphasis on the underlying structures are provided. I personally like the presentation and the material covered in [SHA 08]. I can also mention [LAW 04] (for a light introduction to the syntactic monoid of a language) or the classic [EIL 74]. See also, the survey [YU 97] or [PER 90] for a condensed exposition.

We have already encountered the notion of automaton in several sections of this book: the formal presentation of deterministic automaton first appeared in definition 2.23. Then the extended model with output was given in definition 2.27, Volume 1, to deal with automatic sequences. We will work only with these types of finite machines.