Formal languages, automata and numeration systems

This project was constructed from a course in combinatorics on words that I am giving for the last ten years at the University of Liège.

The goal is not to have an encyclopedic presentation of the subject, but to familiarize the reader with a series of selected topics on words (words, morphisms, factor complexity, Sturmian words, ...). The philosophy is to rigorously present the concepts being illustrated with many examples (particularly in relations to numeration systems or symbolic dynamics). The reader should be able to quickly gain access to current research problems or attend a conference on the subject. Interactions between combinatorics, arithmetic and automata theory are also highlighted.

The book requires little (or no) prerequisites and thus should be accessible to a wide audience (computer scientists/mathematicians, at Master/graduate level).

The book is published by ISTE-Wiley. The publisher has decided to present my work into two volumes containing three chapters each ISBN: 978-1-84821-615-0 and ISBN: 978-1-84821-788-1.

The first volume can be used for a course in one semester in combinatorics of words (e.g. I give regularly the first two chapters to read to my students, the last one serving as complement for the 'advanced' students). The table of contents and the introduction are available here as a pdf file.

The first chapter of volume 1 (83 pages), the index and table of contents are available online (follow the link 'Read Excerpt' on the editor's website).

Volume 1
Chapter 1. Words and Sequences From Scratch Chapter 2. Morphic Words Chapter 3. More Material on Infinite Words

The second volume develops interactions with numeration systems and automata. Thus, automatic sequences and some of their generalizations are described in detail. It also presents many non-standard numeration systems. The last chapter deals with 'automatic' proofs in combinatorics on words. Thus, it explains how, based on a celebrated theorem of B├╝chi, some combinatorial properties, e.g., occurrence of a repetition, of infinite words (such as automatic sequences or Fibonacci word) can be certified algorithmically. This challenging topic is of interest both for mathematicians and computer scientists.

The first chapter of volume 2 (54 pages), the index and table of contents are available online (follow the link 'Read Excerpt' on the editor's website).

Volume 2
Chapter 1. Crash Course on Regular Languages Chapter 2. A Range of Numeration Systems Chapter 3. Logical Framework and Decidability Issues similar presentation webpages on the ISTE pages for volume 1 and for volume 2. I do hope that this book will find a place in the library of your institution or laboratory and, modestly, this book will attract some students and young researchers to these exciting research topics.
Last modified: Thu Nov 27 17:07:03 CET 2014