BASIC NOTIONS OF UNIVERSAL ALGEBRA FOR LANGUAGE THEORY AND GRAPH GRAMMARS


Bruno COURCELLE


Abstract: This paper reviews the basic properties of the equational and recognizable subsets of general algebras; these sets can be seen as generalizations of the context-free and regular languages respectively. This approach, based on Universal Algebra, facilitates the development of the theory of formal languages so as to include the description of sets of finite trees, finite graphs, finite hypergraphs, tuples of words, partially commutative words (also called traces) and other similar finite objects.

Summary:
Introduction
1 Basic notation
2 Many-sorted magmas
3 Polynomial systems and equational sets
4 Recognizable sets
5 Relationships between equational and recognizable sets
6 Inductively computable functions and Parikh's Theorem
7 Guide to the literature
References

Introduction

The context-free and the regular languages are the two main classes of formal languages. We review how their basic concepts can be used for the description of sets of finite objects like trees, graphs, hypergraphs, tuples of words, traces (equivalence classes of words with respect to partial commutation).
Context-free languages are usually defined by grammars, in terms of certain iterated rewritings; they can also be described as the components of the least solutions of certain systems of recursive set equations in languages. Grammars defining trees, graphs, hypergraphs have been introduced. But in each case one faces the problem of deciding which grammars are context-free and which are not; one has to decide among the variants in definitions which are the really important ones. One has also many basic facts to reprove in each case like the decidability of the emptiness problem. By the theorem of Ginsburg and Rice, the context-free languages can be characterized as the components of the least solutions of systems of equations naturally associated with context-free grammars. These systems are mutually recursive definitions of sets of words using set union and extension to sets of the concatenation of words. Similar systems of equations (i.e. of recursive definitions) can be used for sets of finite objects like trees or graphs, provided operations on them generalizing concatenation are defined. As soon as they are formulated in terms of systems of equations, many results concerning context-free grammars can be proved at the Universal Algebra level, and their applicability to context-free grammars of trees or graphs is immediate. We shall develop this view point and survey the main properties of systems of equations that hold in general. The sets defined by these systems will be called the equational sets. They will be our "general context-free" sets. We shall give examples dealing with trees and graphs.
The regular languages can be defined in several equivalent ways: by finite automata (deterministic or not), by rational expressions, by finite congruences. Kleene's theorem states the equivalence of these definitions. When we call these languages "rational" we refer to their descriptions by rational expressions. Following Mezei and Wright we call them "recognizable" in order to refer to their characterization by finite congruences. (Many authors use the term "recognizable" in the context of some notion of automaton). The notion of a rational set makes sense in arbitrary monoids (a rational set is defined by a rational expression). So does that of a recognizable set (defined in terms of finite congruences). However, Kleene's Theorem does not hold in all monoids. In general, we must distinguish the recognizable sets from the rational ones. Furthermore, the notion of a rational set is particular to monoids (see Section 5 for a discussion) whereas the notion of a recognizable one is more general because finite congruences are meaningful in arbitrary algebras. Hence, we shall take the recognizable sets (introduced by Mezei and Wright in their fundamental paper) as our generalization of regular languages. (We use "regular" as a neutral term designating a class of languages without reference to any specific definition technique.) Let us conclude by discussing automata briefly. The notion of a finite automaton extends nicely to trees representing terms but not to graphs (some definitions have been proposed, but they work only for special types of graphs). Furthermore, it has no meaning for abstract algebraic objects. So one cannot use it at a general level.
We shall review the general properties of recognizable sets and their relationships with equational ones. The result stating that the intersection of an equational set and a recognizable one is equational is fundamental and especially useful in constructions concerning context-free graph grammars. We shall also give a general form of Parikh's Theorem, with applications to equational sets of graphs, i.e., to context-free sets of graphs.

This paper assumes a basic knowledge of Formal Language Theory; however, most proofs will be given in detail: it will be clear that they are no more difficult at an abstract level than in concrete cases. Its aim is to collect results that are easily applicable to the equational (generalized context-free) or recognizable (generalized regular) sets of finite objects like trees or graphs. Outside of the scope of this paper are the descriptions of infinite objects (for which some form of topology is needed) and those of finite and infinite ones by logical formulas.

Additional references and a correction:

The finite automata recognizing sets of rooted, unordered, unranked trees were independently defined in:

D. Lugiez, J.L. Moysset, Tree automata help one to solve equational formulae in AC-theories, J. Symb. Computation 18(1994) 297-318.

A related but not identical notion of automaton can be found in:

J. Niehren, A. Podelski, Feature automata and recognizable sets of feature trees, CAAP'93, LNCS 668 (1993) 356-375.

Reference [40] by Pelletier and Sakarovich is in: Information and Computation 88(1990)15-59.