The genesis of this great and beautiful book spans more than 20 years. It collects and unifies many theoretical notions and results published by Bruno Courcelle and others in a large number of articles.

The concept of a language to communicate with a computer, a machine or any kind of device performing operations is at the heart of Computer Science, a field that has truly thrived with the emergence of symbolic programming languages in the 1960s. Formalizing the algorithms that enable computers to calculate an intended result, to control a machine or a robot, to search and find the relevant information in response to a query, and even to imitate the human brain in actions such as measuring risk and making decisions, is the main activity of computer scientists as well as of ordinary computer users.

The languages designed for these tasks, which number by thousands, are defined in the first place by syntactic rules that construct sets of words and to which are then attached meanings. This understanding of a language was first conceived by structural linguists, in particular Nicolaï Troubetskoï, Roman Jacobson and Noam Chomsky, and has transformed Linguistics, the study of natural languages, by giving it new directions. It has also been extended to programming languages, which are artificial languages, and to the Lambda Calculus, one of many languages devised by logicians, among whom we can cite Kurt Gödel, Alonzo Church and Alan Turing, who aspired to standardize mathematical notation and to mechanize proofs.

This chapter presents the main definitions and results of this book and their significance, with the help of a few basic examples. It is written so as to be readable independently of the other chapters. Definitions are sometimes given informally, with simplified notation, and most proofs are omitted. All definitions will be repeated with the necessary technical details in subsequent chapters.

In Section 1.1, we present the notion of equational set of an algebra by using as examples a context-free language, the set of cographs and the set of series-parallel graphs. We also introduce our algebraic definition of derivation trees.

In Section 1.2, we introduce the notion of recognizability in a concrete way, in terms of properties that can be proved or refuted, for every element of the considered algebra, by an induction on any term that defines this element. We formulate a concrete version of the Filtering Theorem saying that the intersection of an equational set and a recognizable one is equational. It follows that one can decide if a property belonging to a finite inductive set of properties is valid for every element of a given equational set. We explain the relationship between recognizability and finite automata on terms.

In Section 1.3, we show with several key examples how monadic second-order sentences can express graph properties. We recall the fundamental equivalence of monadic second-order sentences and finite automata on words and terms.