Alltings algebra

Tabell över länkar

Abstrakt och 1 inledning

2 Grundläggande definitioner och beteckningar

2.1 set

2.2 Sekvenser

2.3 Signaturer och algebror och 2.4 Kategorier

3 Monografier och deras morfismer

4 Limits och Colimits

5 Rita monografier

6 Grafstrukturer och maskinskrivna monografier

7 submonografier och partiella morfismer

8 algebraiska transformationer av monografier

9 Tillskrivna maskinskrivna monografier

10 Slutsatser och referenser

Abstrakt

Monografier är grafliknande strukturer med riktade kanter av obegränsad längd som ligger fritt intill varandra. Standardnoderna representeras som kanter med längden noll. De kan ritas på ett sätt som överensstämmer med standardgrafer och många andra, som E-grafer eller 8-grafer. Kategorin monografier delar många egenskaper med kategorierna grafstrukturer (algebror av monadiska mångsorterade signaturer), förutom att det inte finns någon terminalmonografi. Det är universellt i den meningen att dess segmentkategorier (eller kategorier av maskinskrivna monografier) är likvärdiga med kategorierna av grafstrukturer. Typmonografier uppstår alltså som ett naturligt sätt att specificera grafstrukturer. En detaljerad analys av enkla och dubbla pushout-transformationer av monografier tillhandahålls, och en uppfattning om tillskrivna maskinskrivna monografier som generaliserar maskinskrivna tillskrivna E-grafer analyseras med attributbevarande transformationer.

Nyckelord : Algebraisk graftransformation, grafstrukturer, maskinskrivna grafer

1 Introduktion

Många olika föreställningar om grafer används inom matematik och datavetenskap: enkla grafer, riktade grafer, multigrafer, hypergrafer, etc. En favorituppfattning i sammanhanget av logik och omskrivning är den som också kallas koger, dvs strukturer av formen pN, E, s, tq där N, E är mängder och s som identifierar från E och s, (tdes) målspetsar på varje kant (eller pil). En anledning till detta är att kategorin koger är isomorf till kategorin algebror för den mångsorterade signaturen med två sorters noder och kanter och två operatornamn src och tgt av typkanter Ñ noder. I överensstämmelse med denna tradition menar vi med graf quiver genom hela denna uppsats.

För att på ett bekvämt sätt representera utarbetade datastrukturer är det ofta nödvändigt att berika grafernas struktur med attribut: noder eller kanter kan vara märkta med element från en fast uppsättning, eller med värden tagna i någon algebra, eller med uppsättningar värden som i [1], etc. Ett intressant exempel kan hittas i [2] med begreppet E-grafer, eftersom de också betraktas som noder.

Mer exakt är en E-graf en algebra vars signatur kan representeras av följande graf:

Namnen som ges till sorteringarna och operatorerna hjälper till att förstå strukturen hos E-grafer: kanterna relaterar noderna sinsemellan, nv-kanterna relaterar noderna till värdena och ev-kanterna relaterar kanterna till värdena. Därför innehåller sorteringsvärdena attribut som också är noder. Men då ser vi att i E-grafer ligger ev-kanterna intill kanter. Detta är icke standard, men vi kan fortfarande acceptera sådana strukturer som någon form av graf, om så bara för att vi förstår hur de kan ritas.

Därför verkar sättet att generalisera begreppet grafer innebära en generalisering av signaturen för grafer som betraktas som algebror. Denna väg har följts av Michael L¨owe i [3], där en grafstruktur definieras som en monadisk mångsorterad signatur. I exemplen ovan, och i många exempel som tillhandahålls i [3], har alla operatorer arity 1 och kan därför betraktas som kanter från deras domän till deras intervallsortering. Är detta anledningen till att de kallas grafstrukturer? Men exemplet ovan visar att E-grafer skiljer sig mycket från grafen som representerar deras signatur. Dessutom är det inte lämpligt att vår förståelse av sådana strukturer ska baseras på syntax, dvs på de särskilda namn som ges till sorter och operatorer i signaturen.

Dessutom är det svårt att se hur algebrorna för vissa mycket enkla monadiska signaturer kan tolkas som grafer av någon form. Ta till exempel signaturen av grafer och vänd målfunktionen till tgt : noder Ñ kanter. Sedan finns det en symmetri mellan sorteringsnoder och kanter, vilket innebär att i en algebra av denna signatur skulle noder och kanter vara objekt av samma karaktär. Är detta fortfarande en graf? Kan vi rita det? Ännu värre, om de två sorterna kollapsas till en, betyder det att en nod/kant kan ligga intill sig själv?

Vi kan ta itu med dessa problem genom att begränsa grafstrukturer till någon klass av monadiska signaturer vars algebror garanterat beter sig på ett ortodoxt sätt, t.ex. genom att uppvisa tydligt separerade kanter och noder. Men detta kan vara benäget till godtycke, och det skulle fortfarande ge en annan nackdel: att begreppet grafstruktur inte lätt ger upphov till en kategori. Det är faktiskt svårt att definiera morfismer mellan algebror med olika signaturer, om så bara för att de kan ha hur många bärvågsuppsättningar som helst.

Tillvägagångssättet som används här är snarare att förkasta varje strukturell distinktion mellan noder och kanter, därför att anta en enhetlig vy av noder som kanter med längd 0, och standardkanter som kanter av längd 2 eftersom de ligger intill två noder. Denna enhetliga vy tillåter logiskt att kanter ligger intill alla kanter och inte bara till noder, vilket generaliserar ytterkanterna av E-grafer och till och med till kanter som ligger intill dem själva. Slutligen finns det ingen anledning att begränsa längden på kanter till 0 eller 2, och vi kommer att hitta goda skäl (i avsnitt 6) för att tillåta kanter med oändlig ordningslängd. De nödvändiga begreppen och notationerna introduceras i avsnitt 2. Monografins struktur (tillsammans med morfismer) definieras i avsnitt 3, vilket ger en bestiary av kategorier av monografier enligt några av deras egenskaper. Egenskaperna för dessa kategorier med hänsyn till förekomsten av gränser och samgränser analyseras i avsnitt 4.

Vi ser sedan i avsnitt 5 hur monografier exakt kan representeras av ritningar, givetvis förutsatt att de har ändligt många kanter och att dessa har ändlig längd. I synnerhet motsvarar sådana ritningar standardsättet att rita en graf för de monografier som kan identifieras med standardgrafer, och på liknande sätt för E-grafer.

Avsnitt 6 ägnas åt jämförelsen mellan monografier och grafstrukturer och motsvarande algebror (som vi kan kalla grafstrukturerade algebror). Vi visar en egenskap av universalitet hos monografier, i den meningen att alla grafstrukturerade algebror kan representeras (men vanligtvis inte på ett kanoniskt sätt) som maskinskrivna monografier, dvs. som morfismer av monografier.

Begreppet grafstruktur har introducerats i [3] för att erhålla kategorier av partiella homomorfismer där tekniker för algebraisk grafomskrivning skulle kunna utföras. Korrespondensen med monografier som fastställts i avsnitt 6 kräver en liknande utveckling av partiella morfismer av monografier i avsnitt 7. Metoderna för enkel och dubbel pushout för att skriva om monografier kan sedan definieras, analyseras och jämföras i avsnitt 8.

Begreppet E-graf har introducerats i [2] för att erhålla väluppfostrade kategorier (wrt graph rewriting) av tillskrivna grafer, och därmed för att föreslå lämpliga representationer av verkliga datastrukturer. Detta uppnås genom att berika E-grafer med en datatypalgebra och genom att identifiera noder av sortsvärde med elementen i denna algebra. Vi följer ett liknande tillvägagångssätt i avsnitt 9 med begreppet tillskriven typad monografi genom att identifiera element i en algebra med kanter och få liknande väluppförda kategorier. På grund av monografiernas universalitet ser vi att vilken Σ-algebra som helst kan representeras som en tillskriven maskinskriven monografi.

Vi avslutar i avsnitt 10. Observera att delar av avsnitt 4 till 6 har publicerats i [4].