Graph algebra

The concept of a graph algebra was introduced by G.F. McNulty and C.R. Shallon in 1983. Let ${\displaystyle D=(V,E)}$ be a directed graph (see Graph (data structure)), and let ${\displaystyle 0}$ be an element not in ${\displaystyle V}$. The graph algebra associated with ${\displaystyle D}$ is the set ${\displaystyle V\cup \{0\}}$ equipped with multiplication defined by the rules ${\displaystyle xy=x}$ if ${\displaystyle x,y\in V,(x,y)\in E}$, and ${\displaystyle xy=0}$ if ${\displaystyle x,y\in V\cup \{0\},(x,y)\notin E}$.

Graph algebras have been used in several directions of mathematics and computer science in constructions concerning, for example, dualities, equational theories (equational theory), varieties (variety (universal algebra)), finite state automata or finite state machines, etc.

References

Davey, B.A.; Idziak, P.M.; Lampe W.A.; & McNulty, G.F. (2000). "Dualizability and graph algebras", Discrete Math. 214(1-3), 145-172.

McNulty, G.F.; & Shallon, C.R. (1983). "Inherently nonfinitely based finite algebras". In Universal Algebra and Lattice Theory (Puebla, 1982), Springer, Berlin, 206-231.

Kelarev, A.V. (2003). Graph Algebras and Automata. Marcel Dekker, New York. ISBN: 0-8247-4708-9.

Kelarev, A.V.; & Sokratova, O.V. (2003). "On congruences of automata defined by directed graphs", Theoretical Computer Science 301, 31-43.

Kiss, E.W.; P"oschel, R.; & Pr"ohle, P. (1990). "Subvarieties of varieties generated by graph algebras", Acta Sci. Math. (Szeged) 54(1-2), 57-75.