Recognizable Sets of Graphs, Hypergraphs and Relational Structures: A Survey
---
paper_title: Basic notions of universal algebra for language theory and graph grammars

paper_content:

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.
---
paper_title: The recognizability of sets of graphs is a robust property

paper_content:

Once the set of finite graphs is equipped with an algebra structure (arising from the definition of operations that generalize the concatenation of words), one can define the notion of a recognizable set of graphs in terms of finite congruences. Applications to the construction of efficient algorithms and to the theory of context-free sets of graphs follow naturally. The class of recognizable sets depends on the signature of graph operations. We consider three signatures related respectively to Hyperedge Replacement (HR) context-free graph grammars, to Vertex Replacement (VR) context-free graph grammars, and to modular decompositions of graphs. We compare the corresponding classes of recognizable sets. We show that they are robust in the sense that many variants of each signature (where in particular operations are defined by quantifier-free formulas, a quite flexible framework) yield the same notions of recognizability. We prove that for graphs without large complete bipartite subgraphs, HR-recognizability and VR-recognizability coincide. The same combinatorial condition equates HR-context-free and VR-context-free sets of graphs. Inasmuch as possible, results are formulated in the more general framework of relational structures.
---
paper_title: The recognizability of sets of graphs is a robust property

paper_content:

Once the set of finite graphs is equipped with an algebra structure (arising from the definition of operations that generalize the concatenation of words), one can define the notion of a recognizable set of graphs in terms of finite congruences. Applications to the construction of efficient algorithms and to the theory of context-free sets of graphs follow naturally. The class of recognizable sets depends on the signature of graph operations. We consider three signatures related respectively to Hyperedge Replacement (HR) context-free graph grammars, to Vertex Replacement (VR) context-free graph grammars, and to modular decompositions of graphs. We compare the corresponding classes of recognizable sets. We show that they are robust in the sense that many variants of each signature (where in particular operations are defined by quantifier-free formulas, a quite flexible framework) yield the same notions of recognizability. We prove that for graphs without large complete bipartite subgraphs, HR-recognizability and VR-recognizability coincide. The same combinatorial condition equates HR-context-free and VR-context-free sets of graphs. Inasmuch as possible, results are formulated in the more general framework of relational structures.
---
paper_title: The recognizability of sets of graphs is a robust property

paper_content:

Once the set of finite graphs is equipped with an algebra structure (arising from the definition of operations that generalize the concatenation of words), one can define the notion of a recognizable set of graphs in terms of finite congruences. Applications to the construction of efficient algorithms and to the theory of context-free sets of graphs follow naturally. The class of recognizable sets depends on the signature of graph operations. We consider three signatures related respectively to Hyperedge Replacement (HR) context-free graph grammars, to Vertex Replacement (VR) context-free graph grammars, and to modular decompositions of graphs. We compare the corresponding classes of recognizable sets. We show that they are robust in the sense that many variants of each signature (where in particular operations are defined by quantifier-free formulas, a quite flexible framework) yield the same notions of recognizability. We prove that for graphs without large complete bipartite subgraphs, HR-recognizability and VR-recognizability coincide. The same combinatorial condition equates HR-context-free and VR-context-free sets of graphs. Inasmuch as possible, results are formulated in the more general framework of relational structures.
---

Title: Recognizable Sets of Graphs, Hypergraphs and Relational Structures: A Survey
Section 1: Introduction
Description 1: Introduce the scope of the theory of formal languages extending to graphs, hypergraphs, and relational structures, highlighting its relevance and significance. 

Section 2: Notions from Universal Algebra
Description 2: Explain the fundamental concepts from Universal Algebra that are necessary for dealing with graphs and hypergraphs, including many-sorted algebras, equational sets, and recognizable sets.

Section 3: Graph operations
Description 3: Discuss the different operations on graphs that form the signature for defining equational sets, specifically focusing on HR (Hyperedge Replacement) and VR (Vertex Replacement) operations and their significance.

Section 4: Monadic Second-Order logic and graph properties
Description 4: Explore the use of Monadic Second-Order logic (MS logic) for specifying sets of graphs and graph properties and present fundamental theorems related to MS definable sets and their recognizability.

Section 5: Monadic Second-Order Transductions
Description 5: Describe how Monadic Second-Order transductions are used for transforming graphs and hypergraphs, along with relevant theorems and their implications for equational and recognizable sets.