Content deleted Content added
m Open access bot: hdl added to citation with #oabot. |
fix arv/sfn "no target" errors (x1) + clean up citations |
||
Line 4:
== Definition ==
Let <math>D=(V,E)</math> be a directed [[graph (data structure)|graph]], and <math>0</math> an element not in <math>V</math>. The graph algebra associated with <math>D</math> has underlying set <math>V \cup \{0\}</math>, and is equipped with a multiplication defined by the rules
* <math>xy = x</math> if <math>x,y \in V</math> and <math>(x,y) \in E</math>,
Line 10 ⟶ 9:
== Applications ==
This notion has made it possible to use the methods of graph theory in universal algebra and several other directions of discrete mathematics and computer science. Graph algebras have been used, for example, in constructions concerning dualities {{harv|Davey|Idziak|Lampe|McNulty|2000}}, [[equational theory|equational theories]] {{harv|Pöschel|1989}}, [[flatness (systems theory)|flatness]] {{harv|Delić|2001}}, [[groupoid (algebra)|groupoid]] [[ring (mathematics)|rings]] {{harv|Lee|1991}}, [[topology|topologies]] {{harv|Lee|1988}}, [[variety (universal algebra)|varieties]] {{harv|Oates-Williams|1984}}, [[finite state automata]] {{harv|Kelarev|Miller|Sokratova|2005}}, [[finite state machine]]s {{harv|Kelarev|Sokratova|2003}},
tree languages and [[tree automata]] {{harv|Kelarev|Sokratova|2001}} etc.
Line 19 ⟶ 17:
* [[Path algebra]]
==
{{refbegin|35em}}
*{{Citation| title = Dualizability and graph algebras
| last1 = Davey | first1 = Brian A.
| last2 = Idziak | first2 = Pawel M.
| last3 = Lampe | first3 = William A.
| last4 = McNulty | first4 = George F.
| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
| year = 2000 | volume = 214 | issue = 1 | pages = 145–172
| doi = 10.1016/S0012-365X(99)00225-3 | issn = 0012-365X | mr = 1743633
}}
*{{Citation| title = Finite bases for flat graph algebras
| last = Delić | first = Dejan | year = 2001
| journal = Journal of Algebra
| volume = 246 | issue = 1 | pages = 453–469
| doi = 10.1006/jabr.2001.8947 | issn = 0021-8693 | mr = 1872631
}}
*{{Citation| title = ''Graph Algebras and Automata''
| last = Kelarev | first = A.V. | year = 2003
| publisher = [[Marcel Dekker]] | place = New York
| url = https://archive.org/details/graphalgebrasaut0000kela | url-access = registration
| isbn = 0-8247-4708-9 | mr = 2064147
}}
*{{Citation| title = Languages recognized by two-sided automata of graphs
| last1 = Kelarev | first1 = A.V.
| last2 = Miller | first2 = M.
| last3 = Sokratova | first3 = O.V.
| journal = Proc. Estonian Akademy of Science
| year = 2005 | volume = 54 | issue = 1 | pages = 46–54
| issn = 1736-6046 | mr = 2126358
}}
*{{Citation| title = Directed graphs and syntactic algebras of tree languages
| last1 = Kelarev | first1 = A.V.
| last2 = Sokratova | first2 = O.V.
| journal = J. Automata, Languages & Combinatorics
| year = 2001 | volume = 6 | issue = 3 | pages = 305–311
| issn = 1430-189X | mr = 1879773
}}
*{{Citation| title = On congruences of automata defined by directed graphs
| last1 = Kelarev | first1 = A.V.
| last2 = Sokratova | first2 = O.V.
| journal = Theoretical Computer Science
| year = 2003 | volume = 301 | issue = 1–3 | pages = 31–43
| doi = 10.1016/S0304-3975(02)00544-3 | issn = 0304-3975 | mr = 1975219
}}
*{{Citation| title = Subvarieties of varieties generated by graph algebras
| last1 = Kiss | first1 = E.W.
| last2 = Pöschel | first2 = R.
| last3 = Pröhle | first3 = P.
| journal = Acta Sci. Math. (Szeged)
| year = 1990 | volume = 54 | issue = 1–2 | pages = 57–75
| mr = 1073419
}}
*{{Citation| title = Graph algebras which admit only discrete topologies
| last = Lee | first = S.-M. | year = 1988
| journal = Congr. Numer.
| volume = 64 | pages = 147–156
| issn = 1736-6046 | mr = 0988675
}}
*{{Citation| title = Simple graph algebras and simple rings
| last = Lee | first = S.-M. | year = 1991
| journal = Southeast Asian Bull. Math.
| volume = 15 | issue = 2 | pages = 117–121
| issn = 0129-2021 | mr = 1145431
}}
*{{Citation| chapter = Inherently nonfinitely based finite algebras
| last1 = McNulty | first1 = George F.
| last2 = Shallon | first2 = Caroline R.
| year = 1983
| title = Universal algebra and lattice theory (Puebla, 1982)
| publisher = [[Springer-Verlag]] | ___location = Berlin, New York
| volume = 1004 | series = Lecture Notes in Math.
| pages = [https://archive.org/details/universalalgebra0000unse/page/206 206–231]
| url = https://archive.org/details/universalalgebra0000unse
| doi = 10.1007/BFb0063439 | hdl = 10338.dmlcz/102157 | isbn = 978-3-540-12329-3 | mr = 716184
| hdl-access = free
}}
*{{Citation| title = On the variety generated by Murskiĭ's algebra
| last = Oates-Williams | first = Sheila | year = 1984
| journal = Algebra Universalis
| volume = 18 | issue = 2 | pages = 175–177
| doi = 10.1007/BF01198526 | issn = 0002-5240 | mr = 743465
}}
*{{Citation| title = The equational logic for graph algebras
| last = Pöschel | first = R | year = 1989
| journal = Z. Math. Logik Grundlag. Math.
| volume = 35 | issue = 3 | pages = 273–282
| doi = 10.1002/malq.19890350311 | mr = 1000970
}}
{{refend}}
==Further reading==
{{refbegin}}
*{{Citation| title = Graph algebras
| last = Raeburn | first = Iain | year = 2005
| author-link = Iain Raeburn
| publisher = [[American Mathematical Society]]
| isbn = 978-0-8218-3660-6
| ref = none
}}
{{refend}}
[[Category:Graph theory]]
[[Category:Universal algebra]]
| |||