EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS 2025, Vol. 18, Issue 1, Article Number 5850 ISSN 1307-5543 – ejpam.com Published by New York Business Global On the Recognition Capacity of Abelian Graph Automata Kyriakos Papadopoulos Department of Mathematics, Kuwait University, Safat 13060, Kuwait Abstract. This paper explores the recognition capacity of both unitary and non-unitary Abelian graph automata through the algebraic structure of graphoids. We investigate for the first time in the literature the recognition mechanism of non-unitary Abelian graph automata and prove that they can recognize graph languages which are beyond the recognition power of unitary graph automata. Consequently, we establish that the class of graph languages recognized by unitary automata is strictly contained within the class of those recognized by Abelian graph automata. These results manifest a proper hierarchy among graph automata classes and provide new insights into the recognition capabilities of graph automata. 2020 Mathematics Subject Classifications: 05C20,05C85,68T10,68R10 Key Words and Phrases: Graph Automata, Pattern Recognition, Graph Theory 1. Introduction Graphs serve as powerful tools for modeling relationships and dependencies across var- ious fields from network analysis to artificial intelligence [21], [25], [26], [1]. Automata theory, with its robust framework for recognizing structured data (see [11–14]), can be naturally extended into graph theory, enabling a systematic verification of graph charac- teristics [18],[8]. Central to this approach is the algebraic representation of graphs through magmoids, where the operations of graph product and graph sum are employed to represent graph structures (see [7], [9]) playing a role similar to monoids in string generation. A mag- moid is defined as a doubly ranked set equipped with two operations that are associative, unitary, and canonically distributed [5]. As Engelfriet and Vereijken showed in [15], every graph can be represented in an infinite number of different ways inside a magmoid. To overcome this ambiguity, the algebraic structure of graphoids was introduced in [10] by considering the quotient magmoid obtained via a finite set equivalences. By employing a special type of graphoid, called here unitary graphoid, automata op- erating on graphs were defined for the first time in [10]. As it was shown in [19], uni- tary graphoids are the simplest kind of abelian relational graphoids. The class of abelian DOI: https://doi.org/10.29020/nybg.ejpam.v18i1.5850 Email address: kyriakos.papadopoulos@ku.edu.kw (K. Papadopoulos) https://www.ejpam.com 1 Copyright: © 2025 The Author(s). (CC BY-NC 4.0) K. Papadopoulos / Eur. J. Pure Appl. Math, 18 (1) (2025), 5850 2 of 13 graphoids is in turn included in a larger class of graphoids called relational graphoids which are obtained by appropriately structuring the set of all relations on the state set of the graph automaton into a graphoid [19]. The definition of graph automata given in [10], implies that the recognition capacity of graph automata may vary with respect to the specific graphoid employed in their con- struction. However, this remains an open question, since the recognition mechanism of the various types of graph automata with respect to their underlying graphoid has not been further investigated besides unitary graphoids. Regarding the recognition ability of unitary graph automata, i.e., graph automata employing unitary graphoids, we know that they recognize for every positive integer k, the set of all directed k-colorable graphs with- out inputs and outputs [20]. Graph colorability and the associated chromatic number of a graph is a fundamental concept in graph theory, representing the minimum number of colors required to color the vertices of a graph such that no two adjacent vertices share the same color (see [2–4, 6, 16]). In this respect, it is manifested that graph automata can recognize complex algebraic structures even when operating on the simplest type of graphoid. In this paper, we investigate further unitary graph automata and we prove that the set of directed graphs of length at most k is recognized automata of this type and hence belongs to the associate class of graph languages denoted here by Urec(Σ). Using a similar construction, we also generalize the result of [20] by showing that, for every k, the set of all directed graphs with chromatic number at most k belongs to Urec(Σ). Moreover, in this paper, we examine, for the first time in the literature, abelian non- unitary graph automata. We show that the set of all graphs with an odd number of edges belongs to the class Arec(Σ) of all graph languages recognized by abelian relational graph automata. This is proved by constructing an abelian non-unitary graph automaton with two states that can be structured into a group via the operation of modulo 2 addition, as dictated by the classification theorem of [19]. In addition to that, we prove that unitary graph automata can not recognize this graph language. As a consequence it is proved that Urec(Σ) is properly contained in Arec(Σ). In the next section, we review the fundamental definitions of magmoids and hyper- graphs. Section 3 presents the basic algebraic structures employed for the construction of graph automata and introduces the notions of relational, abelian and unitary graphoids. In the next section, we provide the formal definition of a graph automaton and the different types of graph automata corresponding to the introduced graphoids. Moreover, in this section we construct a unitary graph automaton recognizing the set of all directed graphs with a given chromatic number. In Section 5 we introduce a type of abelian non-unitary graph automaton which recog- nizes all graphs with an odd number of edges. It is then proved that this graph language can not be recognized by a unitary graph automaton establishing the proper hierarchy of the corresponding classes. K. Papadopoulos / Eur. J. Pure Appl. Math, 18 (1) (2025), 5850 3 of 13 2. Magmoids and Hypergraphs In this section we first introduce the algebraic structure of magmoids and then we define directed graphs with specified inputs and outputs. We also present two graph operations, called graph sum and graph product. It turns out that these two operations organize the set of graphs can into a magmoid. Given a set S we denote by S∗ the set of all strings constructed from the elements of S, we denote by ε the empty string, and we set S+ = S∗ − {ε}. A doubly ranked set A = (Am,n)m,n∈N, consists of a set A along with a function rank : A → N× N and is defined as Am,n = {a ∈ A | rank(a) = (m,n)}. For simplicity, we will omit the subscript and denote a doubly ranked set by A = (Am,n). A magmoid is a doubly ranked set M = (Mm,n) equipped with two operations ◦ : Mm,n ×Mn,k → Mm,k, □ : Mm,n ×Mm′,n′ → Mm+m′,n+n′ that are associative in the usual way and satisfy the distributive law (f ◦ g)□ (f ′ ◦ g′) = (f □ f ′) ◦ (g □ g′) whenever the operations are defined. Additionally, there exists a sequence of constants en ∈ Mn,n, called units, such that em ◦ f = f = f ◦ en, e0 □ f = f = f □ e0, em □ en = em+n for all f ∈ Mm,n and all m,n ∈ N. The final equation implies that the elements en are uniquely determined by e1, which we shall denote simply by e. The free magmoid mag(Σ) generated by a doubly ranked set Σ is constructed in [7]. The sets Relm,n(Q) of all relations from Qm to Qn are defined as Relm,n(Q) = {R | R ⊆ Qm ×Qn} and can be structured into a magmoid with ◦ as the usual relational composition and □ defined as follows: for R ∈ Relm,n(Q) and S ∈ Relm′,n′(Q), R□ S = {(u1u2, v1v2) | (u1, v1) ∈ R and (u2, v2) ∈ S}, where u1 ∈ Qm, u2 ∈ Qm′ , v1 ∈ Qn, v2 ∈ Qn′ . Here, Q0 = {ε}, with ε as the empty word of Q∗. The units are defined as e0 = {(ε, ε)} and e = {(g, g) | g ∈ Q}. We denote by Rel(Q) = (Relm,n(Q)) the magmoid constructed in this manner, referred to as the relational magmoid of Q. K. Papadopoulos / Eur. J. Pure Appl. Math, 18 (1) (2025), 5850 4 of 13 An (m,n)-(hyper)graph G = (V,E, s, t, l, begin, end) with edge labels from a doubly ranked set Σ = (Σm,n) is a structure consisting of a finite set of vertices V , a finite set of edges E, the source and target functions s : E → V + and t : E → V +, the labeling function l : E → Σ such that rank(l(e)) = (|s(e)|, |t(e)|) and sequences of begin and end nodes, begin ∈ V ∗ and end ∈ V ∗, with |begin| = m and |end| = n. Note that vertices may repeat in the begin and end sequences, as well as in edge sources and targets. The set of all (m,n)-graphs over Σ is denoted by GRm,n(Σ), and we define GR(Σ) = (GRm,n(Σ))m,n∈N. A path of length n inside a graph G is a sequence of edges e1, . . . , en, such that, for every i < n − 1, there exists a node vi of G, that appears in both the strings t(ei) and s(ei+1). We say that a path e1, . . . , en inside G is a cycle, if there exists a node v of G, that appears in both the strings s(e1) and t(en). The length of a graph G is defined as the length of the longest path inside G, see [17, 24, 27, 28]. Note that if a graph G has a cycle then there will be a path of length n inside G for any n ∈ N. Hence the length of a graph is finite if and only if the graph is acyclic. Ordinary graphs are obtained as a special case of hypergraphs, where each hyperedge is binary, i.e. for every edge e of the graph it holds |s(e)| = |t(e)| = 1. A graph is called unlabeled if every edge has the same label. An ordinary, unlabeled graph is called conventional graph. A graph has no input (resp. output) if the begin (resp. end) sequence is ε. A graph without input and output is by definition a (0, 0)-graph. Conventional (0, 0)-graphs is the most commonly examined type of directed graphs in the literature. The product and the sum of two graphs where introduced by Engelfriet and Vereijken in [15], see also [7, 10, 19]. For an (m,n)-graph G and an (n, k)-graph H, the product G◦H is the (m, k)-graph obtained by taking the disjoint union of the two graphs and identifying the ith end node of G with the ith begin node of H for all i. The begin and end sequences of the product are respectively the begin sequence of G and the end sequence of H. The sum G □ H of two arbitrary graphs G and H is obtained by taking their disjoint union and concatenating their begin and end node sequences. For each n ∈ N, let En represent the discrete graph of rank (n, n) with nodes x1, . . . , xn and begin = end = x1 · · ·xn; we denote E1 simply by E. It is straightforward to verify that GR(Σ) = (GRm,n(Σ)) forms a magmoid with operations product and sum, the units are the graphs En. 3. Graphoids In this section, we explore graph automata by utilizing the algebraic structure of graphoids as defined in [10]. Let Ip,q denote the discrete (p, q)-graph that has a single node x with begin and end sequences both formed by x repeated p and q times, respec- tively. We also let Π be the discrete (2, 2)-graph with two nodes, x and y, whose begin sequence is xy and end sequence is yx. For each σ ∈ Σm,n, we denote by σ the (m,n)-graph with a single edge and m+ n nodes labeled x1, . . . , xm, y1, . . . , yn. The edge is labeled σ, with the begin (resp. end) sequence of the graph as the sequence of sources (resp. targets) of the edge: x1 · · ·xm (resp. y1 · · · yn). Engelfriet and Vereijken, in [15], proposed an algorithm that inductively constructs any graph G ∈ GR(Σ) from the set Σ∪{Π, I01, I21, I10, I12} by using graph product and graph K. Papadopoulos / Eur. J. Pure Appl. Math, 18 (1) (2025), 5850 5 of 13 sum. However, a given graph can be constructed in infinitely many ways. This issue was addressed by identifying a finite set E of equations with the property that two expressions represent the same graph if and only if one can be transformed into the other using these equations [7]. Thus, the equations in E are valid in GR(Σ), and magmoids satisfying this property are referred to as graphoids. Formally, a graphoid M = (M,DM ) consists of a magmoid M and a set DM = {s, d01, d21, d10, d12}, where s ∈ M2,2 and dκλ ∈ Mκ,λ, such that the following equations hold: s ◦ s = e2, (1) (s□ e) ◦ (e□ s) ◦ (s□ e) = (e□ s) ◦ (s□ e) ◦ (e□ s) , (2) (e□ d21) ◦ d21 = (d21 □ e) ◦ d21, (3) (e□ d01) ◦ d21 = e, (4) s ◦ d21 = d21, (5) (e□ d01) ◦ s = (d01 □ e) , (6) (s□ e) ◦ (e□ s) ◦ (d21 □ e) = (e□ d21) ◦ s, (7) d12 ◦ (e□ d12) = d12 ◦ (d12 □ e) , (8) d12 ◦ (e□ d10) = e, (9) d12 ◦ s = d12, (10) s ◦ (e□ d10) = (d10 □ e) , (11) (d12 □ e) ◦ (e□ s) ◦ (s□ e) = s ◦ (e□ d12) , (12) d12 ◦ d21 = e, (13) (d12 □ e) ◦ (e□ d21) = d21 ◦ d12, (14) sm,1 ◦ (p□ e) = (e□ p) ◦ sn,1, for all p ∈ Mm,n. (15) where sm,1 is defined inductively by s and represents the graph associated with the permu- tation that interchanges the last n numbers with the first one [7]. Notably, Equation (15) only needs to hold for elements of Σ to be valid for every element of a magmoid generated by Σ (see [7]). Hence, the pair (GR(Σ), DGR(Σ)) with D = {Π, I01, I21, I10, I12}, is a graphoid and is, in fact, the free graphoid generated by Σ as illustrated in [10]. For graphoids (M,DM ) and (M ′, DM ′), a magmoid morphism H : M → M ′ that preserves D-sets, i.e., H(s) = s′ and H(dκλ) = d′κλ, is called a morphism of graphoids. A graphoid (Rel(Q), DRel(Q)) formed from the magmoid of relations Rel(Q) is called relational graphoid. If the element s ∈ DRel(Q) of a relational graphoid is s = {(g1g2, g2g1) | g1, g2 ∈ Q}, (16) then the pair (Rel(Q), DRel(Q)) is called abelian graphoid (see [19]). K. Papadopoulos / Eur. J. Pure Appl. Math, 18 (1) (2025), 5850 6 of 13 The unitary graphoid U(Q) = (Rel(Q), DU Rel(Q)), which was used for introducing graph automata in [10], is an abelian graphoid constructed by defining, in addition to s as above, the elements d01, d21, d10, d12 as follows d01 = {(ε, g) | g ∈ Q}, (17) d21 = {(gg, g) | g ∈ Q}, (18) d10 = {(g, ε) | g ∈ Q}, (19) d12 = {(g, gg) | g ∈ Q}. (20) In [19] it is proved that a set of states Q can be structured into an abelian graphoid if and only if it can be partitioned into disjoint abelian groups with operations derived from d21 and unit derived from d10 (or equivalently from d12 and d01). In this setup the unitary graphoid U(Q), introduced above, corresponds to the partition of the state set Q = {q1, q2, . . . , qk} into k singleton sets Q = {qi} which can then be structured into k trivial groups. 4. Graph Automata In this section we introduce different types of relational automata operating on graphs, corresponding to different types of relational graphoids. A relational graph automaton, as introduced in [10], is a structure A = (Σ, Q, (Rel(Q), DRel(Q)), δA, IA, TA), where Σ is the doubly ranked set of hyperedge labels, Q is a finite set of states, δA : Σ → Rel(Q) is the doubly ranked transition function, and IA, TA are initial and final rational subsets of Q∗. According to Theorem 3 of [10], the function δA is uniquely extended to a morphism of graphoids δ̄A : GR(Σ) → (Rel(Q), DRel(Q)), where δ̄A(Iij) = dij and δ̄A(Π) = s. The behavior of A is defined by |A| = {F | F ∈ GRm,n(Σ), δ̄A(F ) ∩ (I (m) A × T (n) A ) ̸= ∅, m, n ∈ N}, where I (m) A = IA ∩Qm and T (n) A = TA ∩Qn. Notice that, due to the use of the relational graphoid, the resulting graph automata are non-deterministic. Graph automata can be obtained similarly to the above definition using non-relational graphoids, although this has never been examined in the literature. In the particular case that the relational graphoid satisfies Eq. 16, then the corresponding relational graph automaton is called abelian graph automaton. In addition, if it satisfies Eq. 16 and Eqs.17- 20, it is called unitary graph automaton. The set of all graph languages over the doubly ranked set Σ, recognized by a relational graph automaton is denoted by Rrec(Σ). Analogously, we denote by Arec(Σ) the set of K. Papadopoulos / Eur. J. Pure Appl. Math, 18 (1) (2025), 5850 7 of 13 Figure 1: The class hierarchy of graph automata graph languages recognized by abelian graph automata and by Urec(Σ) the set of graph languages recognized by unitary graph automata. In [20] it was shown that the set of conventional k-colorable graphs without inputs and outputs belongs to Urec(Σ) for every positive integer k. This was achieved by constructing a unitary graph automaton able to read all ordinary (0, 0)-graphs with identical edge labels, and recognize those that can be assigned a proper k-coloring. Next we will construct a unitary graph automaton recognizing all conventional graphs of length at most k. Proposition 1. Given k ∈ N, the set of conventional graphs of length at most k belongs to Urec(Σ). Proof. We are first going to construct a graph automaton recognizing all ordinary unlabeled (0, 0)-graphs of length at most k. Consider the unitary graph automaton Ak len = (Σ, Q,U(Q), δAk len , IAk len , TAk len ) with Σ = Σ1,1 = {a}, state set Q = {1, 2, ..., k + 1}, transition function given by δAk len (a) = {(i, j) | i, j ∈ Q, i < j}, and IAk len = TAk len = {ε}. From this construction we see that any successful transition inside this automaton will increase the state index for each edge of the graph it reads. As a result, by taking into account the path length definition, there will be not successful transition for any graph that has a path of length larger than k but every graph of smaller length will be recognized. H1 H2 H3 Figure 2: Three unlabeled (0, 0)graphs with binary edges K. Papadopoulos / Eur. J. Pure Appl. Math, 18 (1) (2025), 5850 8 of 13 We will illustrate this by examining the three ordinary graphs shown in Figure 2, starting with H1, a graph of length 3. We know that GR(Σ) is the free graphoid, hence the operation of any automaton does not depend to the specific representation of H1 we will employ. Below is a representation of H1 where graph product and graph sum are denoted, for simplicity, by horizontal and vertical concatenation. H1 = I01 a I12 ( a a )( a E ) I21 I10 The image of H1 by the transition function of A3 len is δA3 len (H1) = d01 δA3 len (a) d12 ( δA3 len (a) δA3 len (a) )( δA3 len (a) e ) d21 d10 and an accepting state map for it will be {ε}d01{1}δA3 len (a){2}d12 { 2 2 }( δA3 len (a) δA3 len (a) ){ 3 4 }( δA3 len (a) e ){ 4 4 } d21{4} d10{ε} where the states are indicated in brackets. Hence the graph is recognized by A3 len. Repre- sented on the graph, the states that the automaton reaches at each vertex are 1 2 3 4 The graph H2 of Figure 2 has length 4. We can employ the below representation H2 = I01 a I12 ( a a )( a a ) I21 a I10 and observe that this graph can not be accepted by A3 len since any possible transition can reach at most to the last δA3 len (a) before halting as seen below. {ε}d01{1}δA3 len (a){2}d12 { 2 2 }( δA3 len (a) δA3 len (a) ){ 3 3 }( δA3 len (a) δA3 len (a) ){ 4 4 } d21{4} δA3 len (a) The third graph of Figure 2 has a cycle and hence its length is infinite. A possible representation of H3 is given below. H3 = I01 a I12 ( a E )( a E )( a E ) I21 I10 K. Papadopoulos / Eur. J. Pure Appl. Math, 18 (1) (2025), 5850 9 of 13 From this representation, we see that H3 can not be accepted by A3 len since any transition will halt when reaching d21 as illustrated below. {ε}d01{1}δA3 len (a){2}d12 { 2 2 }( δA3 len (a) e ){ 3 2 }( δA3 len (a) e ){ 4 2 }( δA3 len (a) e ){ 5 2 } d21 The graph automaton A3 len can be generalized to consider every (m,n)-graph if we modify the initial and final sequences by setting IAk len = Qm and TAk len = Qn. This will not affect the behavior of the automaton as it is evident from the Equations 17-20 which hold for every unitary automaton. From the above Proposition we get that the graph language Lenk that consists of all conventional graphs with length at most k lies in the class Urec(Σ), for every positive integer k. Using the same argument as in the end of the above proof we can generalize the result of [20] to obtain the following. Proposition 2. Given k ∈ N, the set of all conventional graphs with chromatic number at most k, belongs to Urec(Σ). 5. Non-unitary abelian graph automata Non-unitary graph automata have never been examined in the literature and their recognition capacity remains unknown. As a result, we don’t know if the class hierarchy depicted in Figure 1 is proper. In this section, we will introduce non-unitary abelian graph automata operating by virtue of graphoids associated to non-trivial groups. We will identify a graph language recognized by such a graph automaton and show that it doesn’t belong to Urec(Σ), demon- strating that Urec(Σ) is properly included in Arec(Σ). For this we define the abelian graphoid G2(0,1) that is obtained by the trivial partition of the set {0, 1} to a single set that is structured into a group via the operation of addition mod 2. + 0 1 0 0 1 1 1 0 From Theorem 3 of [19], we get that the elements of DG2(0,1), besides s will be as follows d21 = {(01, 1), (10, 1)}, d10 = {(0, ε)}, d12 = {(1, 01), (1, 10)}, d01 = {(ε, 0)}. Clearly, graph automata operating on G2(0,1) are abelian but non-unitary. Hence the graph languages they recognize belong to Arec(Σ) but necessarily to Urec(Σ). Now we consider the graph language L (1,1) od of all conventional (1, 1)-graphs with an odd number of edges. We prove the following proposition. K. Papadopoulos / Eur. J. Pure Appl. Math, 18 (1) (2025), 5850 10 of 13 Proposition 3. The graph language L (1,1) od belongs to Arec(Σ). Proof. We use this G2(0,1) to construct the following graph automaton Aod = (Σ, {0, 1},G2(0,1), δAod , IAod , TAod ) with Σ = Σ1,1 = {a}, state set Q = {0, 1}, IAod = {0}, TAod = {1} and the transition function given by δAod (a) = {(0, 1), (1, 0)}. This graph automaton recognizes the graph language L (1,1) od of all conventional (1, 1)- graphs with an odd number of edges. To illustrate this, we consider the following graphs, where the nodes of the begin and end sequences are designated by b1 and e1 respectively. b1 e1 H4 b1 e1 H5 b1 e1 H6 Figure 3: Three unlabeled (1, 1)-graphs with binary edges The image of a representation of H4 by the transition function of Aod gives δ̄Aod (H4) = δAod (a) d12 ( δAod (a) δAod (a) ) d21 and an accepting sequence of states is {0}δAod (a){1}d12 { 1 0 }( δAod (a) δAod (a) ){ 0 1 } d21{1} which shows that H4 is recognized by Aod. Similarly, we can see that for H5 and H6 the following sequences of states can be respectively obtained {0}δAod (a){1}d12 { 1 0 }( δAod (a) δAod (a) ){ 0 1 } d21{1}δAod (a){0} and {0}d12 { 1 0 }( δAod (a) e ){ 0 0 } d21{0}, which shows that H6 is accepted but not H5. Notice that, according to [10], the behavior of the graph automaton will be the same regardless of which representation we select. Next we are going to prove that L(1,1) od does not belong to Urec(Σ), thus obtaining the following Proposition 4. The class Urec(Σ) is properly contained in Arec(Σ). K. Papadopoulos / Eur. J. Pure Appl. Math, 18 (1) (2025), 5850 11 of 13 Proof. Assume that there is a unitary automaton AU od recognizing L (1,1) od and a graph G ∈ L (1,1) od . Then there will be states a ∈ IAU od and b ∈ TAU od , and the following accepting transition. {a}δAU od (G){b} We consider now the graph Gp = I12 ◦ (G□G) ◦ I21, which is accepted by the graph automaton AU od with accepting transition as shown below. {a}d12 { a a }( δAU od (G) δAU od (G) ){ b b } d21{b} This is a contradiction since Gp has an even number of edges. Hence L (1,1) od does not belong to Urec(Σ) and from Proposition 3 we obtain the result. 6. Conclusion We investigated unitary and non-unitary Abelian graph automata by leveraging the al- gebraic structure of graphoids and demonstrated that unitary graph automata effectively recognize sets of directed graphs with chromatic numbers bounded by any given inte- ger, thereby extending existing results in the literature. In addition, we introduced and examined non-unitary Abelian graph automata, showing that they can recognize graph languages—such as graphs the set of conventionawith an odd number of edges—that lie beyond the recognition capabilities of unitary graph automata. This establishes a strict hi- erarchy between the graph languages recognized by these two classes of automata namely, Urec(Σ) ⊂ Arec(Σ). The presented results demonstrate the robust expressive power of non-unitary automata and provide new insights into the interplay between graph automata and their correspond- ing algebraic structures. By showing how variations in the underlying graphoid influence recognition capability, this work paves the way for further exploration of the theoretical and practical implications of graph automata. As a continuation of this study, the recognition mechanisms of non-unitary graph au- tomata derived from graphoids based on non-Abelian groups with more than two elements need to be investigated. Such an exploration could further expand the hierarchy of graph language recognition within the class of Abelian graph automata. Additionally, while con- structing non-Abelian and non-relational graphoids is theoretically feasible, it remains an open problem. The successful development of such machines would enable comparisons with existing unitary and Abelian graph automata, thereby broadening our understanding of the recognition capabilities of graph automata. Moreover, drawing parallels to the string case, we can compare the recognition power of graph automata to the syntactic recognizability of graphs, as introduced in [9]. We can also investigate the possible construction of fuzzy graph automata, similarly to syntactic fuzzy recognition, as described in [22, 23]. K. Papadopoulos / Eur. J. Pure Appl. Math, 18 (1) (2025), 5850 12 of 13 References [1] Shaikh Ibrahim Abdullah, Sovan Samanta, Kajal De, et al. Properties of the forgotten index in bipolar fuzzy graphs and applications. Scientific Reports, 14:28264, 2024. [2] Noga Alon, Janos Pach, and Josef Solymosi. Ramsey-type theorems with forbidden subgraphs. Combinatorica, 21:155–170, 2001. [3] Kenneth Appel and Wolfgang Haken. Every planar map is four colorable. i. discharg- ing. Illinois Journal of Mathematics, 21:429–490, 1977. [4] Kenneth Appel, Wolfgang Haken, and John Koch. Every planar map is four colorable. ii. reducibility. Illinois Journal of Mathematics, 21:491–567, 1977. [5] Andre Arnold and Max Dauchet. Théorie des magmoides. RAIRO Theoret. Inform. Appl., 12:235–257, 1978. [6] Edgar Asplund and Branko Grünbaum. On a coloring problem. Mathematica Scan- dinavica, 8:181–188, 1960. [7] Symeon Bozapalidis and Antonios Kalampakas. An axiomatization of graphs. Acta Inform., 41:19–61, 2004. [8] Symeon Bozapalidis and Antonios Kalampakas. Automata on patterns and graphs. In Proceedings of the 1st Conference on Algebraic Informatics, pages 31–52, 2006. [9] Symeon Bozapalidis and Antonios Kalampakas. Recognizability of graph and pattern languages. Acta Inform., 42:553–581, 2006. [10] Symeon Bozapalidis and Antonios Kalampakas. Graph automata. Theoret. Comput. Sci., 393:147–165, 2008. [11] Sander Bruggink and Barbara König. Recognizable languages of arrows and cospans. Mathematical Structures in Computer Science, 28(8):1290 – 1332, 2018. [12] Bruno Courcelle. On recognizable sets and tree automata. In Algebraic Techniques, pages 93–126. Academic Press, 1989. [13] Alexsander Andrade de Melo and Mateus de Oliveira Oliveira. Second-order finite automata. Theory of Computing Systems, 66(4):861 – 909, 2022. [14] Heinz-Dieter Ebbinghaus and Jörg Flum. Finite Automata and Logic: A Microcosm of Finite Model Theory, pages 107–118. Springer Berlin Heidelberg, 1995. [15] Joost Engelfriet and Jan Joris Vereijken. Context-free graph grammars and concate- nation of graphs. Acta Informatica, 34:773–803, 1997. [16] Paul Erdős. Graph theory and probability. Canadian Journal of Mathematics, 11:34– 38, 1959. [17] Tibor Gallai. On directed paths and circuits. In P. Erdös and G. Katona, editors, Theory of Graphs, pages 115–118. Academic Press, New York, 1968. [18] Antonios Kalampakas. The syntactic complexity of eulerian graphs. Lecture Notes in Computer Science, 4728:208 – 217, 2007. [19] Antonios Kalampakas. Graph automata: The algebraic properties of abelian relational graphoids. Lecture Notes in Computer Science, 7020:168–182, 2011. [20] Antonios Kalampakas. Graph automata and graph colorability. European Journal of Pure and Applied Mathematics, 16(1):112–120, 2023. [21] Antonios Kalampakas. Wardrop optimal networks. Eur. J. Pure Appl. Math., K. Papadopoulos / Eur. J. Pure Appl. Math, 18 (1) (2025), 5850 13 of 13 17(4):2448–2466, 2024. [22] Antonios Kalampakas, Stefanos Spartalis, and Lazaros Iliadis. Syntactic recognizabil- ity of graphs with fuzzy attributes. Fuzzy Sets and Systems, 229:91–100, 2013. [23] Antonios Kalampakas, Stefanos Spartalis, Lazaros Iliadis, and Elias Pimenidis. Fuzzy graphs: algebraic structure and syntactic recognition. Artif. Intell. Rev., 42:479–490, 2014. [24] Chen-Yu Lin. Simple proofs of results on paths representing all colors in proper vertex-colorings. Graphs and Combinatorics, 23:201–203, 2007. [25] Rupkumar Mahapatra, Sovan Samanta, Madhumangal Pal, et al. A study on linguistic z-graph and its application in social networks. Mathematics, 12(18):2898, 2024. [26] Jambi Ratna Raja, Jeong Gon Lee, Dhanraj Dhotre, et al. Fuzzy graphs and their applications in finding the best route, dominant node and influence index in a network under the hesitant bipolar-valued fuzzy environment. Complex & Intelligent Systems, 10(4):5195–5211, 2024. [27] Bernard Roy. Nombre chromatique et plus longs chemins d’un graph. Rev. AFIRO, 1:127–132, 1967. [28] Douglas West. Introduction to Graph Theory. Prentice-Hall, New Jersey, 1996. Introduction Magmoids and Hypergraphs Graphoids Graph Automata Non-unitary abelian graph automata Conclusion