Graph algebra: Difference between revisions

Revision as of 14:51, 12 February 2021

Revision as of 00:18, 8 May 2021

Line 1:

{{Use Harvard referencing|date=August 2020}}

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

{{Format footnotes|date=January 2021|reason=Parenthetical referencing has been [[WP:PARREF|deprecated]]; convert to [[Help:Shortened footnotes|shortened footnotes]].}}

__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 inby McNulty and Shallon,{{harvr|McNulty|Shallon|1983McNultyShallon1983}}, and has seen many uses in the field of universal algebra since then.

== Definition ==

Line 11 ⟶ 10:

== 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 ,{{harvr|Davey|Idziak|Lampe|McNulty|2000DaveyETAL2000}}, [[equational theory|equational theories]] ,{{harvr|Pöschel|1989Pöschel1989}}, [[flatness (systems theory)|flatness]] ,{{harvr|Delić|2001Delić2001}}, [[groupoid (algebra)|groupoid]] [[ring (mathematics)|rings]] ,{{harvr|Lee|1991Lee1991}}, [[topology|topologies]] ,{{harvr|Lee|1988Lee1988}}, [[variety (universal algebra)|varieties]] ,{{harvr|Oates-Williams|1984Williams1984}}, [[finite state automata]] ,{{harv|Kelarev|Miller|Sokratovar|2005KelarevMillerSokratova2005}}, [[finite state machine]]s ,{{harvr|Kelarev|Sokratova|2003KelarevSokratova2003}},

tree languages and [[tree automata]] ,{{harvr|Kelarev|Sokratova|2001KelarevSokratova2001}} etc.

== See also ==

Line 21 ⟶ 20:

==Works cited==

{{refbegin|35em}}

{{reflist|refs=

*{{Citation| title = Dualizability and graph algebras

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

| last1 = Davey | first1 = Brian A.

| last2 = Idziak | first2 = Pawel M.

<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 |pp=145–172 |issn=0012-365X |doi=10.1016/S0012-365X(99)00225-3 |mr=1743633 }}</ref>

| last3 = Lampe | first3 = William A.

| last4 = McNulty | first4 = George F.

<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 |pp=273–282 |doi=10.1002/malq.19890350311 |mr=1000970}}</ref>

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

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

<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 |pp=453–469 |issn=0021-8693 |doi=10.1006/jabr.2001.8947 |mr=1872631}}</ref>

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

}}

<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 |pp=117–121 |issn=0129-2021 |mr=1145431}}</ref>

*{{Citation| title = Finite bases for flat graph algebras

| last = Delić | first = Dejan | year = 2001

<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 |pp=147–156 |issn=1736-6046 |mr=0988675}}</ref>

| journal = Journal of Algebra

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

<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 |pp=175–177 |issn=0002-5240 |doi=10.1007/BF01198526 |mr=743465 |s2cid=121598599}}</ref>

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

}}

<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 |pp=46–54 |issn=1736-6046 |mr=2126358}}</ref>

*{{Citation| title = ''Graph Algebras and Automata''

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

<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 |pp=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>

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

| url = https://archive.org/details/graphalgebrasaut0000kela | url-access = registration | via = [[Internet Archive]]

<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 |pp=305–311 |issn=1430-189X |mr=1879773}}</ref>

| isbn = 0-8247-4708-9 | mr = 2064147

}}{{refend}}

}}

*{{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

| url = https://eprints.utas.edu.au/157/1/congruences.pdf

| 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 | via = [[Internet Archive]]

| 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 | s2cid = 121598599

}}

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

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

*{{Citation| title = Graph algebras

* {{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 |pp=57–75 |mr=1073419}}

| last = Raeburn | first = Iain | year = 2005

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

| author-link = Iain Raeburn

| publisher = [[American Mathematical Society]]

| isbn = 978-0-8218-3660-6

| ref = none

}}

{{refend}}