Content deleted Content added
Graphalgebra (talk | contribs) added link tree automata |
ce |
||
| (46 intermediate revisions by 30 users not shown) | |||
Line 1:
{{about|the mathematical concept of Graph Algebras|"Graph Algebra" as used in the social sciences|Graph algebra (social sciences)}}
{{Use shortened footnotes|date=May 2021}}
In [[mathematics]], especially in the fields of [[universal algebra]] and [[graph theory]], a '''graph algebra''' is a way of giving a [[directed graph]] an [[algebraic structure]]. It was introduced by McNulty and Shallon,{{sfn|McNulty|Shallon|1983|loc=[https://archive.org/details/universalalgebra0000unse/page/206 pp. 206–231]}} and has seen many uses in the field of universal algebra since then.
== Definition ==
Let {{math|1=''D'' = (''V'', ''E'')}} be a directed [[graph (data structure)|graph]], and {{math|0}} an element not in {{mvar|V}}. The graph algebra associated with {{mvar|D}} has underlying set <math>V \cup \{0\}</math>, and is equipped with a multiplication defined by the rules
* {{math|1=''xy'' = ''x''}} if <math>x,y \in V</math> and <math>(x,y) \in E</math>,
* {{math|1=''xy'' = 0}} if <math>x,y \in V \cup \{0\}</math> and <math>(x,y)\notin E</math>.
== Applications ==
This notion has made it possible to use the methods of graph theory in universal algebra and several other areas of [[discrete mathematics]] and [[computer science]]. Graph algebras have been used, for example, in constructions concerning [[Dual (category theory)|dualities]],{{sfn|Davey|Idziak|Lampe|McNulty|2000|pp=145–172}} [[equational theory|equational theories]],{{sfn|Pöschel|1989|pp=273–282}} [[flatness (systems theory)|flatness]],{{sfn|Delić|2001|pp=453–469}} [[groupoid (algebra)|groupoid]] [[ring (mathematics)|rings]],{{sfn|Lee|1991|pp=117–121}} [[topology|topologies]],{{sfn|Lee|1988|pp=147–156}} [[variety (universal algebra)|varieties]],{{sfn|Oates-Williams|1984|pp=175–177}} [[finite-state machine]]s,{{sfn|Kelarev|Miller|Sokratova|2005|pp=46–54}}{{sfn|Kelarev|Sokratova|2003|pp=31–43}}
tree languages and [[tree automata]],{{sfn|Kelarev|Sokratova|2001|pp=305–311}} etc.
== See also ==
* [[Group algebra (disambiguation)]]
* [[Incidence algebra]]
* [[Path algebra]]
==
{{Reflist|20em}}
==Works cited==
{{refbegin|35em}}
*{{Cite journal | 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
| doi-access = free }}
*{{Cite journal | title = Finite bases for flat graph algebras
| last = Delić | first = Dejan
| journal = [[Journal of Algebra]]
| year = 2001 | volume = 246 | issue = 1 | pages = 453–469
| doi = 10.1006/jabr.2001.8947 | issn = 0021-8693 | mr = 1872631
| doi-access = free
}}
*{{Cite journal | 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
}}
*{{Cite journal | 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
}}
*{{Cite journal | 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
| url = https://eprints.utas.edu.au/157/1/congruences.pdf
| doi = 10.1016/S0304-3975(02)00544-3 | issn = 0304-3975 | mr = 1975219
}}
*{{Cite journal | title = Graph algebras which admit only discrete topologies
| last = Lee | first = S.-M.
| journal = Congr. Numer
| year = 1988 | volume = 64 | pages = 147–156
| issn = 1736-6046 | mr = 0988675
}}
*{{Cite journal | title = Simple graph algebras and simple rings
| last = Lee | first = S.-M.
| journal = Southeast Asian Bull. Math
| year = 1991 | volume = 15 | issue = 2 | pages = 117–121
| issn = 0129-2021 | mr = 1145431
}}
*{{Cite book| 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)
| editor1-last = Freese | editor1-first = Ralph S.
| editor2-last = Garcia | editor2-first = Octavio C.
| publisher = [[Springer-Verlag]] | ___location = Berlin, New York City
| volume = 1004 | series = Lecture Notes in Math.
| at = [https://archive.org/details/universalalgebra0000unse/page/206 pp. 206–231]
| url = https://archive.org/details/universalalgebra0000unse | via = [[Internet Archive]]
| doi = 10.1007/BFb0063439 | hdl = 10338.dmlcz/102157 | isbn = 978-354012329-3 | mr = 716184
| hdl-access = free
}}
*{{Cite journal | title = On the variety generated by Murskiĭ's algebra
| last = Oates-Williams | first = Sheila
| author-link = Sheila Oates Williams
| journal = [[Algebra Universalis]]
| year = 1984 | volume = 18 | issue = 2 | pages = 175–177
| doi = 10.1007/BF01198526 | issn = 0002-5240 | mr = 743465 | s2cid = 121598599
}}
*{{Cite journal | title = The equational logic for graph algebras
| last = Pöschel | first = R.
| journal = Z. Math. Logik Grundlag. Math.
| year = 1989 | volume = 35 | issue = 3 | pages = 273–282
| doi = 10.1002/malq.19890350311 | mr = 1000970
}}
{{refend}}
==Further reading==
{{refbegin}}
*{{Cite book| title = Graph Algebras and Automata
| last = Kelarev | first = A.V. | year = 2003
| publisher = [[Marcel Dekker]] | place = New York City
| url = https://archive.org/details/graphalgebrasaut0000kela | url-access = registration | via = [[Internet Archive]]
| isbn = 0-8247-4708-9 | mr = 2064147
| ref = none
}}
*{{cite journal | 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.
| year = 1990 | volume = 54 | issue = 1–2 | pages = 57–75
| mr = 1073419
| ref = none
}}
*{{Cite book| title = Graph algebras
| last = Raeburn | first = Iain | year = 2005
| publisher = [[American Mathematical Society]]
| isbn = 978-082183660-6
| ref = none
}}
{{refend}}
[[Category:Graph theory]]
[[Category:Universal algebra]]
| |||