This text is devoted to the theory of varieties, which provides an important tool, based in universal algebra, for the classification of regular languages. In the introductory section, we present a number of examples that illustrate and motivate the
fundamental concepts. We do this for the most part without proofs, and often without precise definitions, leaving these to the formal development of the theory that begins in Section 2. Our presentation of the theory draws heavily on the work of Gehrke, Grigorieff and Pin (2008) on the equational theory of lattices of regular languages. In the subsequent sections we consider in more detail aspects of varieties that were only briefly evoked in the introduction: Decidability, operations on languages, and characterizations in formal logic.
We show that one can define and effectively compute Stallings graphs for quasi-convex subgroups of automatic groups (textit{e.g.} hyperbolic groups or right-angled Artin groups). These Stallings graphs are finite labeled graphs, which are canonically
associated with the corresponding subgroups. We show that this notion of Stallings graphs allows a unified approach to many algorithmic problems: some which had already been solved like the generalized membership problem or the computation of a quasi-convexity constant (Kapovich, 1996); and others such as the computation of intersections, the conjugacy or the almost malnormality problems. Our results extend earlier algorithmic results for the more restricted class of virtually free groups. We also extend our construction to relatively quasi-convex subgroups of relatively hyperbolic groups, under certain additional conditions.
