Graph algebra: Difference between revisions

Revision as of 04:37, 23 May 2021

Latest revision as of 10:32, 29 September 2024

(9 intermediate revisions by 8 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}}

__NOTOC__

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,{{rsfn|McNultyShallon1983McNulty|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 ==

Line 10:

== Applications ==

This notion has made it possible to use the methods of graph theory in universal algebra and several other directionsareas of [[discrete mathematics]] and [[computer science]]. Graph algebras have been used, for example, in constructions concerning [[Dual (category theory)|dualities]],{{rsfn|Davey|Idziak|Lampe|McNulty|2000|DaveyETAL2000pp=145–172}} [[equational theory|equational theories]],{{rsfn|Pöschel1989Pöschel|1989|pp=273–282}} [[flatness (systems theory)|flatness]],{{rsfn|Delić2001Delić|2001|pp=453–469}} [[groupoid (algebra)|groupoid]] [[ring (mathematics)|rings]],{{rsfn|Lee1991Lee|1991|pp=117–121}} [[topology|topologies]],{{rsfn|Lee1988Lee|1988|pp=147–156}} [[variety (universal algebra)|varieties]],{{rsfn|Oates-Williams1984Williams|1984|pp=175–177}} [[finite -state automatamachine]]s,{{rsfn|KelarevMillerSokratova2005Kelarev|Miller|Sokratova|2005|pp=46–54}} [[finite state machine]]s,{{rsfn|Kelarev|Sokratova|2003|KelarevSokratova2003pp=31–43}}

tree languages and [[tree automata]],{{rsfn|KelarevSokratova2001Kelarev|Sokratova|2001|pp=305–311}} etc.

== See also ==

Line 17:

* [[Incidence algebra]]

* [[Path algebra]]

==Citations==

{{Reflist|20em}}

==Works cited==

{{refbegin|35em}}

*{{Cite journal | title = Dualizability and graph algebras

{{reflist|refs=

| last1 = Davey | first1 = Brian A.

<ref name=McNultyShallon1983>{{Cite book |last1=McNulty |first1=George F. |last2=Shallon |first2=Caroline R. |year=1983 |chapter=Inherently nonfinitely based finite algebras |editor-last1=Freese |editor-first1=Ralph S. |editor-last2=Garcia |editor-first2=Octavio C. |title=Universal algebra and lattice theory (Puebla, 1982) |volume=1004 |series=Lecture Notes in Math. |___location=Berlin, New York City |publisher=[[Springer-Verlag]] |at=[https://archive.org/details/universalalgebra0000unse/page/206 pp. 206–231] |isbn=9783540123293 |doi=10.1007/BFb0063439 |hdl=10338.dmlcz/102157 |mr=716184 |hdl-access=free |url=https://archive.org/details/universalalgebra0000unse |via=[[Internet Archive]]}}</ref>

| last2 = Idziak | first2 = Pawel M.

| last3 = Lampe | first3 = William A.

<ref name=DaveyETAL2000>{{Cite journal |last1=Davey | first1=Brian A. |last2=Idziak |first2=Pawel M. |last3=Lampe |first3=William A. |last4=McNulty |first4=George F. |date=2000 |title=Dualizability and graph algebras |journal=[[Discrete Mathematics (journal)|Discrete Mathematics]] |volume=214 |issue=1 |pages=145–172 |issn=0012-365X |doi=10.1016/S0012-365X(99)00225-3 |mr=1743633 }}</ref>

| last4 = McNulty | first4 = George F.

| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]

<ref name=Pöschel1989>{{Cite journal |last=Pöschel |first=R. |date=1989 |title=The equational logic for graph algebras |journal=Z. Math. Logik Grundlag. Math. |volume=35 |issue=3 |pages=273–282 |doi=10.1002/malq.19890350311 |mr=1000970}}</ref>

| year = 2000 | volume = 214 | issue = 1 | pages = 145–172

| doi = 10.1016/S0012-365X(99)00225-3 | issn = 0012-365X | mr = 1743633

<ref name=Delić2001>{{Cite journal |last=Delić |first=Dejan |date=2001 |title=Finite bases for flat graph algebras |journal=Journal of Algebra |volume=246 |issue=1 |pages=453–469 |issn=0021-8693 |doi=10.1006/jabr.2001.8947 |mr=1872631}}</ref>

| doi-access = free }}

*{{Cite journal | title = Finite bases for flat graph algebras

<ref name=Lee1991>{{Cite journal |last=Lee |first=S.-M. |date=1991 |title=Simple graph algebras and simple rings |journal=Southeast Asian Bull. Math. |volume=15 |issue=2 |pages=117–121 |issn=0129-2021 |mr=1145431}}</ref>

| last = Delić | first = Dejan

| journal = [[Journal of Algebra]]

<ref name=Lee1988>{{Cite journal |last=Lee |first=S.-M. |date=1988 |title=Graph algebras which admit only discrete topologies |journal=Congr. Numer. |volume=64 |pages=147–156 |issn=1736-6046 |mr=0988675}}</ref>

| year = 2001 | volume = 246 | issue = 1 | pages = 453–469

| doi = 10.1006/jabr.2001.8947 | issn = 0021-8693 | mr = 1872631

<ref name=Oates-Williams1984>{{Cite journal |last=Oates-Williams |first=Sheila |date=1984 |title=On the variety generated by Murskiĭ's algebra |journal=Algebra Universalis |volume=18 |issue=2 |pages=175–177 |issn=0002-5240 |doi=10.1007/BF01198526 |mr=743465 |s2cid=121598599}}</ref>

| doi-access = free

}}

<ref name=KelarevMillerSokratova2005>{{Cite journal |last1=Kelarev |first1=A.V. |last2=Miller |first2=M. | last3=Sokratova |first3=O.V. |date=2005 |title=Languages recognized by two-sided automata of graphs |journal=Proc. Estonian Akademy of Science |volume=54 |issue=1 |pages=46–54 |issn=1736-6046 |mr=2126358}}</ref>

*{{Cite journal | title = Languages recognized by two-sided automata of graphs

| last1 = Kelarev | first1 = A.V.

<ref name=KelarevSokratova2003>{{Cite journal |last1=Kelarev |first1=A.V. |last2=Sokratova |first2=O.V. |date=2003 |title=On congruences of automata defined by directed graphs |journal=Theoretical Computer Science |volume=301 |issue=1–3 |pages=31–43 |doi=10.1016/S0304-3975(02)00544-3 |issn=0304-3975 |mr=1975219 |url=https://eprints.utas.edu.au/157/1/congruences.pdf }}</ref>

| last2 = Miller | first2 = M.

| last3 = Sokratova | first3 = O.V.

<ref name=KelarevSokratova2001>{{Cite journal |last1=Kelarev |first1=A.V. |last2=Sokratova |first2=O.V. |date=2001 |title=Directed graphs and syntactic algebras of tree languages |journal=J. Automata, Languages & Combinatorics |volume=6 |issue=3 |pages=305–311 |issn=1430-189X |mr=1879773}}</ref>

| journal = Proc. Estonian Akademy of Science

}}{{refend}}

| 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

* {{Cite book |last=Kelarev |first=A.V. |date=2003 |title=''Graph Algebras and Automata'' |place=New York City |publisher=[[Marcel Dekker]] |isbn=0-8247-4708-9 |mr=2064147 |url-access=registration |via=[[Internet Archive]] |url=https://archive.org/details/graphalgebrasaut0000kela}}

| last = Kelarev | first = A.V. | year = 2003

* {{cite journal |last1=Kiss |first1=E.W. |last2=Pöschel |first2=R. |last3=Pröhle |first3=P. |date=1990 |title=Subvarieties of varieties generated by graph algebras |journal=Acta Sci. Math. |volume=54 |issue=1–2 |pages=57–75 |mr=1073419}}

| publisher = [[Marcel Dekker]] | place = New York City

* {{Cite book |last=Raeburn |first=Iain |date=2005 |title=Graph algebras |publisher=[[American Mathematical Society]] |isbn=9780821836606}}

| 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}}