# Fuzzy Graph Language Recognizability

Antonios Kalampakas, Stefanos Spartalis, Lazaros Iliadis

► To cite this version:

Antonios Kalampakas, Stefanos Spartalis, Lazaros Iliadis. Fuzzy Graph Language Recognizability. 8th International Conference on Artificial Intelligence Applications and Innovations (AIAI), Sep 2012, Halkidiki, Greece. pp.196-205, 10.1007/978-3-642-33409-2_21. hal-01521451

HAL Id: hal-01521451

https://inria.hal.science/hal-01521451

Submitted on 11 May 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Fuzzy Graph Language Recognizability

Antonios Kalampakas<fnref n="1" />*, Stefanos Spartalis<fnref n="1" /> and Lazaros Iliadis<fnref n="2" />

**Abstract.** Fuzzy graph language recognizability is introduced along the lines of the established theory of syntactic graph language recognizability by virtue of the algebraic structure of magmoids. The main closure properties of the corresponding class are investigated and several interesting examples of fuzzy graph languages are examined.

## 1 Introduction

Fuzzy models are becoming increasingly useful because of their ability to bridge the difference between the traditional numerical models used in engineering and sciences and the symbolic models used in formal systems and Artificial Intelligence. In this respect, fuzzy graphs are the appropriate mathematical object capable of modeling real time systems where the inherent level of information in them varies with different levels of precision. In this paper we present for the first time a syntactic recognizability theory for fuzzy hypergraph languages, analogously with the already established theory for crisp hypergraph languages [9, 13].

*Directed hypergraphs* consist of a set of vertices (nodes) and a set of hyperedges, just as ordinary directed graphs except that a hyperedge may have an arbitrary sequence of sources (incoming arrows) and an arbitrary sequence of targets (outgoing arrows), instead of only one source and one target as is the case for ordinary graph edges. Each hyperedge is labeled with a symbol from a doubly ranked alphabet $\Sigma$ in such a way that the first (resp. second) rank of its label equals the number of its sources (resp. targets). Also, every hypergraph is equipped with a sequence of *begin* and *end* nodes. It is clear that ordinary directed graphs are obtained as a special case of directed hypergraphs i.e. in the case that each hyperedge has one source and one target and both the sequences of *begin* and *end* nodes are the empty word. *Directed fuzzy graphs* were

<footnote n="1">¹ Department of Production Engineering and Management, Laboratory of Computational Mathematics, School of Engineering, Democritus University of Thrace, V.Sofias 12, Prokat, Building A1, 67100Xanthi, Greece, akalampakas@gmail.com, sspart@pme.duth.gr</footnote>

<footnote n="2">² Department of Forestry & Management of the Environment & Natural Resources, Democritus University of Thrace, 193 Pandazidou st., 68200, Nea Orestiada, Greece</footnote>

<footnote>* The author has been co-financed by the European Social Fund and Greek national funds through the Operational Program "Education and Lifelong Learning" of the National Strategic Reference Framework - Research Funding Program: THALIS project "Algebraic Modeling of Topological and Computational Structures and Applications"</footnote>
introduced by Rosenfeld in [19] by taking fuzzy subsets of the node and edge
sets of a given directed crisp graph (see also [17]). In [15] Engelfriet and Verei-
jken proved that every graph can be constructed from a finite set of elementary
graphs by inductively using the operations of concatenation and sum. Since for
every graph an infinite number of such expressions exist, at the same paper, the
authors stated the open problem of finding a complete set of equations (rewriting
rules) with the property that two expressions represent the same graph if and
only if one can be transformed into the other by these equations. We solved this
problem in [8] by appropriately adopting magmoids as the necessary algebraic
structure for the representation of graphs and graph operations. This result led
to the introduction of graphoids and in the construction, for the first time, of
automata operating on arbitrary graphs (cf. [10],[16]). A magmoid is a doubly
ranked set endowed with the operations of concatenation and sum which are
associative, unitary, and compatible to each other ([1,2]). They simulate the
ordinary monoid structure and a natural regularity notion derives from this sim-
ulation. More precisely, we say that a subset $L$ of a magmoid $M$ is recognizable
whenever there exist a locally finite magmoid $N$ and a morphism of magmoids
$h: M \to N$, so that $L = h^{-1}(P)$ for some $P \subseteq N$ ([9]). We note that this is
a global recognizability notion (sort independent), whereas the corresponding
notion for many sorted algebras is local since it refers to a specified sort. As
a consequence, although the set of all graphs is magmoid recognizable, this is
not the case for the corresponding graph language in the framework of many
sorted algebras. This recognizability mode is straightforwardly applied to graph
languages and the class of recognizable graph languages is shown to be closed
under boolean operations, inverse magmoid morphisms and sum operation.

The syntactic recognizability mechanism described above is analogous with
the corresponding recognizability notion for string and tree languages. Fuzzy
recognizability for strings and trees has already been introduced in [5–7] by
virtue of syntactic monoids and syntactic algebras respectively. In the present
paper we extend the magmoid recognizability mechanism to languages consist-
ing of directed fuzzy graphs in the previously defined manner. In Section 2 we
present the basic notations, definitions and facts that we will employ later on.
In the same section we introduce fuzzy hypergraphs, their definition is derived
from the one given by Rosenfeld for fuzzy graphs [19]. In the next section we in-
troduce fuzzy graph language recognizability a characterization result obtained
from their underlying magmoid structure is presented and their basic properties
are investigated. It turns out that fuzzy graph language recognizability has nice
closure properties, several interesting examples are examined and their relation
with the corresponding case for crisp graphs is discussed.

## 2 The Algebraic Structure of Fuzzy Graphs

Given a finite set $X$ we denote by $X^*$ the set of all words over $X$, and for
every word $w \in X^*$, $|w|$ denotes its length. A fuzzy set is a pair $X_\chi = (X, \chi)$
where $\chi: X \to [0,1]$ is its *membership function*. A doubly ranked set, or doubly
ranked alphabet, $(A_{m,n})_{m,n \in \mathbb{N}}$ is a set $A$ together with a function $rank: A \to \mathbb{N} \times \mathbb{N}$, where $\mathbb{N}$ is the set of natural numbers. For $m, n \in \mathbb{N}$, $A_{m,n} = \{a \in A \mid rank(a) = (m, n)\}$. In what follows we will drop the subscript $m, n \in \mathbb{N}$ and denote a doubly ranked set simply by $A = (A_{m,n})$. A fuzzy $(m, n)$-graph $G = (V_{\kappa}, E_{\lambda}, s, t, l, begin, end)$ over the doubly ranked alphabet $\Sigma = (\Sigma_{m,n})$ consists of

- the fuzzy sets of nodes or vertices $V_{\kappa} = (V, \kappa)$ and edges $E_{\lambda} = (E, \lambda)$;

- the source and target functions $s: E \to V^*$ and $t: E \to V^*$;

- the labeling function $l: E \to \Sigma$ with $rank(l(e)) = (|s(e)|, |t(e)|)$ for all $e \in E$;

- the sequences of begin and end nodes $begin \in V^*$ and $end \in V^*$ with $|begin| = m$ and $|end| = n$.

with the additional requirement that for every $e \in E$,

$$ \lambda(e) \leq \min\{\kappa(v) \mid v \text{ appears in the words } s(e) \text{ or } t(e)\}. \quad (1) $$

For every $v \in V$ and every $e \in E$ the values $\kappa(v)$ and $\lambda(e)$ are called respectively the membership grade of $v$ and $e$. The above is a generalization for hypergraphs of the definition of fuzzy graphs given by Rosenfeld in [19]. Notice that according to this definition vertices can be duplicated in the begin and end sequences of the graph and also at the sources and targets of an edge. For an edge $e$ of a hypergraph $G$ we simply write $rank(e)$ to denote $rank(l(e))$. The specific sets $V$ and $E$ chosen to define a concrete fuzzy graph $G$ are actually irrelevant. We shall not distinguish between two isomorphic fuzzy graphs. Hence we have the following definition of an abstract graph. Two concrete fuzzy $(m, n)$-graphs $G = (V_{\kappa}, E_{\lambda}, s, t, l, begin, end)$ and $G' = (V'_{\kappa'}, E'_{\lambda'}, s', t', l', begin', end')$ over $\Sigma$ are isomorphic if and only if there exist two bijections $h_V: V \to V'$ and $h_E: E \to E'$ commuting with $\kappa, \lambda, s, t, l, begin$ and $end$ in the usual way. An abstract fuzzy $(m, n)$-graph is defined to be the equivalence class of a concrete fuzzy $(m, n)$-graph with respect to isomorphism. We denote by $FGR_{m,n}(\Sigma)$ the set of all abstract fuzzy $(m, n)$-graphs over $\Sigma$. Since we shall mainly be interested in abstract fuzzy graphs we simply call them graphs. Any graph $G \in FGR_{m,n}(\Sigma)$ with $E = \emptyset$ is called a discrete $(m, n)$-graph.

Given a fuzzy graph $G = (V_{\kappa}, E_{\lambda}, s, t, l, begin, end)$, the fuzzy complement $G^{fc}$ of $G$ is the fuzzy graph $(V_{\kappa'}, E_{\lambda'}, s, t, l, begin, end)$ with

$$ \lambda'(e) = \min\{\kappa(v) \mid v \text{ appears in the words } s(e) \text{ or } t(e)\} - \lambda(e) $$

for all $e \in E$. This graph is well defined due to Eq. (1). We note that this is a generalization of the definition for the complement of a crisp graph. Given a fuzzy graph language $L \subseteq FGR(\Sigma)$ we set $L^{fc} = \{G^{fc} \mid G \in L\}$ i.e. $L^{fc}$ consists of all the fuzzy complements of the elements of $L$.

A magmoid (cf. [1, 2]) is a doubly ranked set $M = (M_{m,n})$ equipped with two operations denoted by $\circ$ (circle) and $\square$ (box):

$$ \circ : M_{m,n} \times M_{n,k} \to M_{m,k}, \quad \square : M_{m,n} \times M_{m',n'} \to M_{m+m',n+n'} $$
for all $m, n, k, m', n' \ge 0$, which are associative in the obvious way and satisfy the distributivity law $(f \circ g) \sqcap (f' \circ g') = (f \sqcap f') \circ (g \sqcap g')$ whenever all the above operations are defined. Moreover, it is equipped with a sequence of constants $e_n \in M_{n,n}$ ($n \ge 0$), called units, such that

$$e_m \circ f = f = f \circ e_n, \quad e_0 \sqcap f = f = f \sqcap e_0$$

for all $f \in M_{m,n}$ and all $m, n \ge 0$, and the additional condition $e_m \sqcap e_n = e_{m+n}$ holds true for all $m, n \ge 0$. Notice that, due to the last equation, the elements $e_n$ ($n \ge 2$) are uniquely determined by $e_1$. From now on $e_1$ will be simply denoted by $e$. Submagmoids, morphisms, congruences and quotients of magmoids are defined in the obvious way.

An elegant characterization of a congruence can be achieved by means of the notion of the context. In a magmoid $M$ an $(m,n)$-context is a 4-tuple $\omega = (g_1, f_1, f_2, g_2)$, with $f_i \in M_{m_i, n_i}$ ($i = 1, 2$), $g_1 \in M_{a, m_1 + m + m_2}$, $g_2 \in M_{n_1 + n + n_2, b}$, where $a, b \in N$. The set of all $(m, n)$-contexts is denoted $\text{Cont}_{m,n}(M)$. For any $f \in M_{m,n}$ and $\omega = (g_1, f_1, f_2, g_2)$ as above, we write $\omega[f] = g_1 \circ (f_1 \sqcap f \sqcap f_2) \circ g_2$; note that $\omega[f] \in M_{a,b}$. As it is shown in [9]

**Proposition 1.** The equivalence $\sim = (\sim_{m,n})$ on the magmoid $M = (M_{m,n})$ is a congruence whenever, for all $m, n \ge 0$, $f, g \in M_{m,n}$ and all $\omega \in \text{Cont}_{m,n}(M)$

$$f \sim_{m,n} g \text{ implies } \omega[f] \sim_{a,b} \omega[g].$$

The set of fuzzy graphs $\text{FGR}(\Sigma) = (\text{FGR}_{m,n}(\Sigma))$ can be organized into a magmoid by virtue of two operations: product and sum corresponding to $\circ$ and $\sqcap$ respectively. If $G$ is an $(m, n)$-graph and $H$ is an $(n, k)$-graph represented respectively by $(V_\kappa, E_\lambda, s, t, l, \text{begin}, \text{end})$ and $(V'_{\kappa'}, E'_{\lambda'}, s', t', l', \text{begin'}, \text{end'})$, then their product $G \circ H$ is the $(m, k)$-graph $(V''_{\kappa''}, E''_{\lambda''}, s'', t'', l'', \text{begin''}, \text{end''})$ obtained by taking the disjoint union of $G$ and $H$ and then identifying the $i^{th}$ end node $v$ of $G$ with the $i^{th}$ begin node $v'$ of $H$, for all $i \in \{1, ..., n\}$; for the resulting node $v''$ we set $\kappa''(v'') = \max\{\kappa(v), \kappa(v')\}$. Additionally, $\text{begin''} = \text{begin}$ and $\text{end''} = \text{end}$. The sum $G \sqcap H$ of arbitrary graphs $G$ and $H$ is their disjoint union with their sequences of begin nodes concatenated and similarly for their end nodes.

For instance let $\Sigma = \{a, b, c\}$, with $\text{rank}(a) = (2, 1)$, $\text{rank}(b) = (1, 1)$ and $\text{rank}(c) = (1, 2)$. In the following pictures, edges are represented by boxes, nodes by dots, and the sources and targets of an edge by directed lines that enter and leave the corresponding box, respectively. The order of the sources and targets of an edge is the vertical order of the directed lines as drawn in the pictures. We display two graphs $G \in \text{FGR}_{3,4}(\Sigma)$ and $H \in \text{FGR}_{4,2}(\Sigma)$, where the $i^{th}$ begin node is indicated by $b_i$, and the $i^{th}$ end node by $e_i$.

<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>
Then their product $G \circ H$ and their sum $G \square H$ are respectively the (3, 2) and the (7, 6)-graphs

<figure><img src="image_4.png" /></figure>

For every $n \in \mathbb{N}$ we denote by $E_n$ the discrete $(n, n)$-graph with nodes $x_1, \dots, x_n$, begin and end sequence $x_1 \cdots x_n$ and $\kappa(x_i) = 0$ for all $i$; we write $E$ for $E_1$. It can be verified that $FGR(\Sigma) = (FGR_{m,n}(\Sigma))$ with the operations defined above is a magmoid, whose units are the graphs $E_n, n \ge 0$.

In what follows we will need the next concepts. Let $M = M_{m,n}$ be a magmoid. We say that a doubly ranked family $L = (L_{m,n})$ is a subset of $M$ (notation $L \subseteq M$), whenever $L_{m,n} \subseteq M_{m,n}$ for all $m, n \in \mathbb{N}$. The boolean operations on subsets of $M$ are defined in the obvious way. Given subsets $L, L'$ of a magmoid $M$ (with unit sequence $e_n$) we define their $\circ$-product $L \circ L'$ by setting

$$ (L \circ L')_{m,n} = \bigcup_{k \ge 0} L_{m,k} \circ L'_{k,n}, \quad m, n \in \mathbb{N} $$

and their $\square$-product $L \square L'$ by setting

$$ (L \square L')_{m,n} = \bigcup_{\substack{\kappa+\kappa'=m \\ \lambda+\lambda'=n}} L_{\kappa,\lambda} \square L'_{\kappa',\lambda'}, \quad m, n \in \mathbb{N}. $$

The subsets $E$ and $F$ of $M$ given by $E_{m,n} = \{e_n\}$ if $m=n$ and $\emptyset$ else, while $F_{m,n} = \{e_0\}$ if $m=n=0$ and $\emptyset$ else, are the units of the operations $\circ$ and $\square$ respectively. The reader will verify that the set of all subsets of $M$ together with $\cup, \circ, \square$ is a double semiring.

## 3 Fuzzy Language Recognizability

Let $X = (X_{m,n})$ be a doubly ranked alphabet. We denote by $mag(X) = (mag_{m,n}(X))$ the free magmoid generated by $X$ its elements are called patterns (see [9]). We say that two elements of a magmoid $M$ are equivalent modulo the syntactic congruence of a subset $L \subseteq M$, whenever they have the same set of contexts with respect to $L$. More precisely, let $L$ be a subset of the magmoid $M$ and $f \in M_{m,n}$, we set $C_L(f) = \{\omega | \omega \in Cont_{m,n}(M), \omega[f] \in L\}$.

**Proposition 2 (cf. [9]).** The equivalence $\sim_L$ on $M$ defined by

$$ f \sim_{L,m,n} g, \quad \text{whenever } C_L(f) = C_L(g) $$
is a congruence.

Given a magmoid $M$ and a set $L \subseteq M$, $\sim_L$ is called the syntactic congruence of $L$ and the quotient magmoid $M_L = M / \sim_L$ is the syntactic magmoid of $L$. Thus, for all $m, n \ge 0$, the set $(M_L)_{m,n}$ can be identified with the set consisting of all distinct contexts of the elements of $M_{m,n}$, i.e., we may write $(M_L)_{m,n} = \{C_L(f) | f \in M_{m,n}\}$ whereas, the operations of $M_L$ are given by the formulas:

$$C_L(f) \circ C_L(g) = C_L(f \circ g), \quad C_L(f) \sqcap C_L(g) = C_L(f \sqcap g).$$

The syntactic magmoid is characterized by the following universal property: for any magmoid epimorphism $H : M \to N$, such that $H^{-1}(H(L)) = L$, there exists a unique magmoid morphism $\tilde{H} : N \to M_L$ such that $\tilde{H} \circ H = H_L$, where $H_L : M \to M_L$ is the canonical projection onto the quotient. Thus $M_L$ is unique up to isomorphism. For magmoids $M, N$, we write $M < N$ whenever $M$ is a quotient of a submagmoid of $N$.

**Proposition 3 (cf. [9]).** Let $F : M \to N$ be a magmoid morphism, $L \subseteq N$ and $L_1, L_2 \subseteq M$, it holds:

i) $M_{L_1 \cap L_2} < M_{L_1} \times M_{L_2}$, $M_{L_1 \cup L_2} < M_{L_1} \times M_{L_2}$, $M_{L_1^c} = M_{L_1}$, where $L^c$ stands for the set-theoretic complement of $L$;

ii) $M_{F^{-1}(L)} < N_L$, if moreover $F$ is surjective, then the syntactic magmoid $M_{F^{-1}(L)}$ is isomorphic with $N_L$.

Recognizability of magmoid subsets is defined in [9] by suitably adapting monoid recognizability. We say that a congruence $\sim = (\sim_{m,n})$ on a magmoid $M = (M_{m,n})$ saturates $L \subseteq M$ whenever, for all $m, n \ge 0$, the subset $L_{m,n}$ is a union of $\sim_{m,n}$-classes. If, for all $m, n \ge 0$, the congruence $\sim_{m,n}$ has finite index (i.e., finite number of equivalence classes) we say that $\sim$ has locally finite index. Moreover, a magmoid $M = (M_{m,n})$ is said to be locally finite if, for all $m, n \ge 0$, the set $M_{m,n}$ is finite.

**Definition 1.** A subset $L$ of $FGR(\Sigma)$ is called recognizable if there exists a locally finite magmoid $N = (N_{m,n})$ (i.e., $N_{m,n}$ finite for all $m, n \in \mathbb{N}$) and a morphism $H : FGR(\Sigma) \to N$, so that $L = H^{-1}(P)$, for some $P \subseteq N$.

We denote by $Rec(FGR(\Sigma))$ the class of all recognizable subsets of $FGR(\Sigma)$. The elements of $Rec(FGR(\Sigma))$ are called recognizable fuzzy graph languages. From this definition and from the construction of the syntactic magmoid, similarly with crisp graph language recognizability of [9], we obtain

**Theorem 1.** Let $L \subseteq FGR(\Sigma)$, the following conditions are equivalent:

1. $L$ is recognizable;

2. $L$ is saturated by a congruence of a locally finite index;

3. $\sim_L$ has locally finite index;

4. the set $\text{card}\{C_L(G) | G \in FGR_{m,n}(\Sigma)\}$ is finite for all $m, n \in \mathbb{N}$;

5. the syntactic magmoid $FGR(\Sigma)_L$ is locally finite.
**Corollary 1.** The class Rec(FGR(Σ)) of all recognizable fuzzy graph languages is closed under finite union, intersection, complement and inverse morphisms of magmoids.

*Proof.* Combine the above theorem with Proposition 3 of [9].

**Proposition 4.** Let Σ be a doubly ranked alphabet and a, b ∈ Σ, a ≠ b, the fuzzy graph language L<sub>k</sub><sup>a,b</sup> ⊆ FGR(Σ) consisting of all graphs that have an equal number of labels a and b on edges with memebeship grade greater or equal to k, k ∈ [0, 1], is not recognizable

*Proof.* For every $G \in FGR(\Sigma)$ and every $\omega = (G_1, F_1, F_2, G_2)$ we denote by $|G|_a$ the number of a's occurring as labels of edges with membership grade greater or equal to k in G and

$$|\omega|_a = |G_1|_a + |F_1|_a + |F_2|_a + |F_2|_a.$$

Let $G \in FGR(\Sigma)$, we observe that for every $\omega, \omega' \in C_{L_k^{a,b}}(G)$ it holds

$$|\omega|_a - |\omega|_b = |\omega'|_a - |\omega'|_b = |G|_b - |G|_a.$$

We can easily verify that the function

$$G \xrightarrow{\phi_{m,n}} |G|_b - |G|_a, \quad G \in GR_{m,n}(\Sigma)$$

is a bijection of the set $(FGR(\Sigma)_{L_k^{a,b}})_{m,n}$ on the set of integers $\mathbb{Z}$. Furthermore it holds

$$\phi(G \circ G') = \phi(G) + \phi(G'), \quad \phi(G \sqcap G') = \phi(G) + \phi(G') \quad \text{and} \quad \phi(E_n) = 0_{n,n}$$

and thus, the syntactic magmoid of $L_k^{a,b}$ is isomorphic to the magmoid associated with the commutative monoid of the additive integers. Since this is locally infinite from Theorem 1 we derive that this language is not recognizable.

**Remark 1.** Note that $L_0^{a,b}$ consists of all fuzzy graphs with an equal number of a's and b's. As we have shown in [9], the syntactic magmoid of the crisp graph language that consists of all graphs with an equal number of a's and b's in their labels, is also isomorphic with the same magmoid and in this respect the present result constitutes a generalization for fuzzy graph languages.

**Proposition 5.** The fuzzy graph language $L_1 \subseteq FGR(\Sigma)$ consisting of all graphs that have exactly k edges ($k \ge 1$) with membership grade 1 is recognizable.

*Proof.* For every $G \in FGR(\Sigma)$ let $|G|_1$ be the number of edges of G with membership grade 1 and for every $\omega = (G_1, F_1, F_2, G_2)$ we set

$$|\omega|_1 = |G_1|_1 + |F_1|_1 + |F_2|_1 + |F_2|_1.$$

It holds:

- $|G|_1 = 0$, whenever for every $\omega \in C_{L_1}(G)$, $|\omega|_1 = k$,
- $|G|_1 = 1$, whenever for every $\omega \in C_{L_1}(G)$, $|\omega|_1 = k - 1$,

- $|G|_1 = k - 1$, whenever for every $\omega \in C_{L_1}(G)$, $|\omega|_1 = 1$,

- $|G|_1 = k$, whenever for every $\omega \in C_{L_1}(G)$, $|\omega|_1 = 0$,

- $|G|_1 \ge k + 1$, whenever $C_{L_1}(G) = \emptyset$.

The function $\phi_{m,n} : (FGR(\Sigma)_{L_1})_{m,n} \to \{0, 1, \dots, k, \alpha\}$, sending the syntactic class of every graph $G \in FGR(\Sigma)_{m,n}$ to $0, 1, \dots, k$ or $\alpha$, whenever $|G|_1 = 0, 1, \dots, k$ or $\ge k + 1$ respectively, is a bijection.

Now let $M(A) = (M(A)_{m,n})$ be the magmoid associated with the commutative monoid $A = \{0, 1, \dots, k, \alpha\}$ whose operation is given by the following table.

<table><tr><td>+</td><td>0</td><td>1</td><td>...</td><td>k</td><td>&alpha;</td></tr><tr><td>0</td><td>0</td><td>1</td><td>...</td><td>k</td><td>&alpha;</td></tr><tr><td>1</td><td>1</td><td>2</td><td>...</td><td>&alpha;</td><td>&alpha;</td></tr><tr><td>&#8942;</td><td>&#8942;</td><td>&#8942;</td><td>...</td><td>&#8942;</td><td>&#8942;</td></tr><tr><td>k</td><td>k</td><td>&alpha;</td><td>...</td><td>&alpha;</td><td>&alpha;</td></tr><tr><td>&alpha;</td><td>&alpha;</td><td>&alpha;</td><td>...</td><td>&alpha;</td><td>&alpha;</td></tr></table>

It holds:

$$ \phi(G \circ G') = \phi(G) + \phi(G'), \quad \phi(G \sqcap G') = \phi(G) + \phi(G') \quad \text{and} \quad \phi(E_n) = 0_{n,n} $$

and hence the syntactic magmoid of $L_1$ is isomorphic to $M(A)$. This is a locally finite magmoid and hence from Theorem 1 we deduce that $L_1 \in \text{Rec}(FGR(\Sigma))$.

**Proposition 6.** *Given a finite doubly ranked set $\Sigma$, the class $\text{Rec}(FGR(\Sigma))$ is closed under $\square$-operation.*

*Proof.* Similar with the corresponding proof for crisp graph languages (see [9]).

Given a fuzzy graph $G = (V_k, E_\lambda, s, t, l, \text{begin}, \text{end})$ we say that there exists a path from the node $v_1$ to the node $v_k$ of $G$ if there exist edges $e_1, \dots, e_{k-1}$ and nodes $v_2, \dots, v_{k-1}$ of $G$ such that $v_i$ appears in $s(e_i)$ and $v_{i+1}$ appears in $t(e_i)$ for all $i = 1, \dots, k-1$.

**Proposition 7.** *The fuzzy graph language $L_{\text{path}} \subseteq FGR_{1,1}(\Sigma)$ that consists of all graphs that have at least one path from the begin node to the end node through edges with membership grade 1 is recognizable.*

*Proof.* We define the following equivalence on $FGR_{m,n}(\Sigma)$: $G_1 \sim_p G_2$ whenever the next two items are equivalent there exists a path from the $i^{th}$ begin node of $G_1$ to the $j^{th}$ end node of $G_1$ through edges with membership grade 1 if and only if there exists a path from the $i^{th}$ begin node of $G_2$ to the $j^{th}$ end node of $G_2$ through edges with membership grade 1. It holds:

$$ G_1 \sim_p G_2 \text{ and } G'_1 \sim_p G'_2 \text{ implies } G_1 \sqcap G'_1 \sim_p G_2 \sqcap G'_2 $$

and similarly for $\circ$, hence $\sim_p$ is a congruence which trivially saturates $L_{\text{path}}$ and thus by Theorem 1 we get that $L_{\text{path}}$ is recognizable.
Fuzzy graph language recognizability can also be characterized through left derivatives in a result that is a generalization of the fundamental fact that a string language is recognizable, if and only if, it has finitely many left derivatives, if and only if, it has finitely many right derivatives (cf. [14]). Let $L \subseteq FGR(\Sigma)$ and $\omega \in Cont_{m,n}(FGR(\Sigma))$. The left derivative of $L$ at $\omega$ is defined as

$$ \omega^{-1}L = \{G \in FGR_{m,n}(\Sigma) | \omega[G] \in L\}. $$

**Proposition 8.** The fuzzy graph language $L \subseteq FGR(\Sigma)$ is recognizable, if and only if, $\text{card}\{\omega^{-1}L | \omega \in Cont_{m,n}(FGR(\Sigma))\} < \infty$, for all $m, n \in \mathbb{N}$.

*Proof.* As in the case of crisp graph languages (see Proposition 5 of [9])

By virtue of this proposition we prove the following result.

**Proposition 9.** Let $L \subseteq FGR(\Sigma)$ be a fuzzy graph language consisting only of graphs that have nodes with membership grade 1, then $L$ is recognizable if and only if $L^{fc}$ is recognizable.

*Proof.* Assume that $L \in \text{Rec}(FGR(\Sigma))$ and $m, n \in \mathbb{N}$, then by the previous proposition

$$ \text{card}\{\omega^{-1}L | \omega \in Cont_{m,n}(FGR(\Sigma))\} < \infty. $$

Let $\omega_1^{-1}L, \dots, \omega_k^{-1}L$ be representatives of the distinct left derivatives of $L$. We shall prove that $(\omega_1^{fc})^{-1}L, \dots, (\omega_k^{fc})^{-1}L$ are all the distinct left derivatives of $L^{fc}$. For every $\omega = (G_1, F_1, F_2, G_2)$, we set

$$ \omega^{fc} = (G_1^{fc}, F_1^{fc}, F_2^{fc}, G_2^{fc}). $$

Note that for any graph $G \in FGR(\Sigma)$ it holds $(G^{fc})^{fc} = G$. Now, let $\omega \in Cont_{m,n}(FGR(\Sigma))$, then for any graph $G \in FGR(\Sigma)$ it holds

$$ \omega[G] \in L^{fc} \Leftrightarrow (\omega[G])^{fc} \in L \Leftrightarrow \omega^{fc}[G^{fc}] \in L. $$

Since we assumed that $\omega_1^{-1}L, \dots, \omega_k^{-1}L$ are all the distinct left derivatives of $L$, from the last we deduce that there exists $1 \le i \le k$ such that

$$ \omega_i[G^{fc}] \in L \Leftrightarrow (\omega_i[G^{fc}])^{fc} \in L^{fc} \Leftrightarrow \omega_i^{fc}[G] \in L^{fc}. $$

Hence the context $\omega$ is identified with one of $\omega_1^{fc}, \dots, \omega_k^{fc}$, and thus $L^{fc}$ has finite distinct left derivatives which by Proposition 8 concludes the proof. Notice that in the equivalences $\Leftrightarrow$ we used the equality $(\omega[G])^{fc} = \omega^{fc}[G^{fc}]$ which holds only in the case that the graph $G$ has only nodes with membership grade 1.

# 4 Conclusion

We introduced a notion of fuzzy graph language recognizability based on the established concept of crisp graph language recognizability and similar with the corresponding theory for string and tree languages. In this respect, existing applications and methods in various areas including model checking and formal verification [3, 4], syntactic complexity [11, 12], and natural language processing [18] can be investigated in the framework of fuzzy graphs.
References

1. Arnold, A., Dauchet, M.: Théorie des magmoides. I. RAIRO Inform. Théor. 12, 235-257 (1978)

2. Arnold, A., Dauchet, M.: Théorie des magmoides. II. RAIRO Inform. Théor. 13, 135-154 (1979)

3. Blume, C.: Recognizable Graph Languages for the Verification of Dynamic Systems. LNCS, vol. 6372, pp. 384-387. Springer (2010)

4. Blume, C., Bruggink, S., König B.: Recognizable Graph Languages for Checking Invariants. Workshop on Graph Transformation and Visual Modeling Techniques, Electronic Communications of the EASST 29, (2010)

5. Bozapalidis, S., Bozapalidou, O.L.: On the recognizability of fuzzy languages I. Fuzzy Sets and Systems 157, 2394-2402 (2006)

6. Bozapalidis, S., Bozapalidou, O.L.: On the recognizability of fuzzy languages II. Fuzzy Sets and Systems 159, 107-113 (2008)

7. Bozapalidis, S., Bozapalidou, O.L.: Fuzzy tree language recognizability. Fuzzy Sets and Systems 161, 716-734 (2010)

8. Bozapalidis, S., Kalampakas, A.: An Axiomatization of Graphs. Acta Inform. 41, 19-61 (2004)

9. Bozapalidis, S., Kalampakas, A.: Recognizability of graph and pattern languages. Acta Inform. 42, 553-581 (2006)

10. Bozapalidis, S., Kalampakas, A.: Graph Automata. Theoret. Comput. Sci. 393, 147-165 (2008)

11. Brzozowski, J., Ye, Y.: Syntactic Complexity of Ideal and Closed Languages. LNCS, vol. 6795, pp. 117128. Springer (2011)

12. Brzozowski, J., Li, B., Ye, Y.: Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages. Theoret. Comput. Sci. (2012) http://dx.doi.org/10.1016/j.tcs.2012.04.011

13. Courcelle, B.: The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs. Inform. and Comput. 85, 12-75 (1990)

14. Eilenberg, S.: Automata, Languages and Machines, vol. A, Academic Press, (1974)

15. Engelfriet, J., Vereijken, J.J.: Context-free graph grammars and concatenation of graphs. Acta Inform. 34, 773-803 (1997)

16. Kalampakas, A.: Graph Automata: The Algebraic Properties of Abelian Relational Graphoids. LNCS, vol. 7020, pp. 168-182. Springer (2011)

17. Mordeson, J.N., Nair, P.S.: Fuzzy Graphs and Fuzzy Hypergraphs. Physica-Verlag, Heidelberg, (2000)

18. Quernheim, D., Knight, K.: Towards Probabilistic Acceptors and Transducers for Feature Structures. In Proc. 6th Workshop Syntax, Semantics and Structure in Statistical Translation. Association for Computational Linguistics, 2012. http://www.ims.uni-stuttgart.de/daniel/pub2/quekni12.pdf

19. Rosenfeld, A.: Fuzzy graphs. in: L.A. Zadeh, K.S. Fu, K. Tanaka, M. Shimura (Eds.), Fuzzy Sets and Their Applications to Cognitive and Decision Processes, Academic Press, New York, 7795 (1975)