Алгебра на сè

Табела со врски

Апстракт и 1 Вовед

2 Основни дефиниции и нотации

2.1 Сетови

2.2 Секвенци

2.3 Потписи и алгебри и 2.4 Категории

3 Монографии и нивните морфизми

4 Ограничувања и Колимити

5 Цртање монографии

6 Структури на графикони и типизирани монографии

7 Подмонографии и парцијални морфизми

8 Алгебарски трансформации на монографии

9 Припишани отчукувани монографии

10 Заклучок и референци

Апстракт

Монографиите се структури слични на графикони со насочени рабови со неограничена должина кои се слободно соседни една до друга. Стандардните јазли се претставени како рабови со должина нула. Тие можат да бидат нацртани на начин што е во согласност со стандардните графикони и многу други, како што се Е-графиците или 8-графиците. Категоријата монографии споделува многу својства со категориите на структури на графикони (алгебри на монадски повеќесортирани потписи), освен што нема терминална монографија. Тој е универзален во смисла дека неговите категории на парчиња (или категории на типизирани монографии) се еквивалентни на категориите структури на графикони. Така, типските монографии се појавуваат како природен начин за специфицирање на структурите на графиконите. Обезбедена е детална анализа на трансформациите на монографии со единечна и двојна истиснување, а се анализира и идејата за атрибутирани типизирани монографии кои ги генерализираат напишените атрибутирани Е-графици со зачувување на атрибутите трансформации.

Клучни зборови : алгебарска трансформација на графикони, графички структури, отчукувани графикони

1 Вовед

Многу различни поими на графикони се користат во математиката и компјутерската наука: едноставни графици, насочени графикони, мултиграфи, хиперграфи, итн. Еден омилен поим во контекст на логиката и препишувањето е оној кој е исто така познат како трепетли, т.е. структури од формата pN, E, s, tq каде N, E се множества и s, T се идентификуваат множества и s, t се идентификуваат функциите од s, t се врвови на секој раб (или стрелка). Една од причините за ова е што категоријата на треперите е изоморфна во однос на категоријата на алгебри на многу сортиран потпис со два вида јазли и рабови и две имиња на оператори src и tgt од типот рабови Ñ јазли. Во согласност со оваа традиција, под графикон подразбираме треперење низ овој труд.

Со цел практично да се претстават елаборираните структури на податоци, често е неопходно да се збогати структурата на графиконите со атрибути: јазлите или рабовите може да се означат со елементи од фиксно множество или со вредности земени во некоја алгебра, или со множества вредности како во [1] итн. Интересен пример може да се најде во [2] со поимот Е-графи, исто така, се сметаат како атрибути без.

Поточно, Е-граф е алгебра чиј потпис може да се претстави со следниот график:

Имињата дадени на сортите и операторите помагаат да се разбере структурата на Е-графиците: рабовите ги поврзуваат јазлите меѓу себе, nv-рабовите ги поврзуваат јазлите со вредностите, а рабовите ev ги поврзуваат рабовите со вредностите. Оттука, вредностите за сортирање содржат атрибути кои исто така се јазли. Но, тогаш гледаме дека во Е-графиците ev-рабовите се соседни со рабовите. Ова е нестандардно, но сепак може да ги прифатиме таквите структури како некаква форма на график, само затоа што разбираме како може да се нацртаат.

Оттука, начинот на генерализирање на поимот графикони се чини дека вклучува генерализација на потписот на графиконите кои се сметаат како алгебри. Овој пат е следен од Мајкл Лоу во [3], каде структурата на графикот е дефинирана како монадичен потпис со повеќе сортирани. Навистина во горенаведените примери, и во многу примери дадени во [3], сите оператори имаат аритност 1 и затоа може да се сметаат како рабови од нивниот домен до сортирањето на опсегот. Дали ова е причината зошто тие се нарекуваат графички структури? Но, примерот погоре покажува дека Е-графиците се многу различни од графиконот што го претставува нивниот потпис. Освен тоа, не е погодно нашето разбирање за таквите структури да се заснова на синтакса, т.е. на одредени имиња дадени на сортите и операторите во потписот.

Понатаму, тешко е да се види како алгебрите на некои многу едноставни монадски потписи може да се толкуваат како графикони од која било форма. Земете го на пример потписот на графиконите и превртете ја целната функција во tgt : јазли Ñ рабови. Потоа, постои симетрија помеѓу сортите јазли и рабови, што значи дека во алгебра од овој потпис јазли и рабови би биле објекти од иста природа. Дали е ова сè уште графикон? Можеме ли да го нацртаме? Уште полошо, ако двата вида се склопат во еден, дали тоа значи дека јазолот/работ може да биде блиску до себе?

Можеме да ги решиме овие проблеми со ограничување на структурите на графиконот на некоја класа монадски потписи чии алгебри гарантирано се однесуваат на православен начин, да речеме со прикажување јасно одвоени рабови и јазли. Но, ова би можело да биде склоно кон самоволие, а сепак би претставувало уште еден недостаток: дека поимот структура на графикот не предизвикува лесно категорија. Навистина, тешко е да се дефинираат морфизми помеѓу алгебри со различни потписи, само затоа што тие можат да имаат било кој број на множества носители.

Пристапот што е усвоен овде е повеќе да се отфрли каква било структурна разлика помеѓу јазлите и рабовите, па оттука да се усвои унифициран поглед на јазлите како рабови со должина 0, и стандардните рабови како рабови со должина 2, бидејќи тие се во непосредна близина на два јазли. Овој унифициран приказ логично дозволува рабовите да бидат во непосредна близина на кои било рабови, а не само до јазлите, со што се генерализираат ev-рабовите на Е-графиците, па дури и до рабовите што се соседни сами на себе. Конечно, нема причина да се ограничи должината на рабовите на 0 или 2, и ќе најдеме добри причини (во делот 6) да дозволиме рабови со бесконечна, редовна должина. Потребните поими и нотации се воведени во делот 2. Структурата на монографијата (заедно со морфизмите) е дефинирана во делот 3, при што се добива бестијар на категории на монографии според некои од нивните карактеристики. Својствата на овие категории во врска со постоењето на лимити и ко-ограничувања се анализирани во Дел 4.

Потоа гледаме во делот 5 како монографиите можат точно да се претстават со цртежи, под услов, се разбира, да имаат конечно многу рабови и да имаат конечна должина. Особено, ваквите цртежи одговараат на стандардниот начин на цртање график за оние монографии кои можат да се идентификуваат со стандардни графикони, а слично и за Е-графиците.

Делот 6 е посветен на споредбата помеѓу монографиите и структурите на графиконите, и соодветните алгебри (кои можеме да ги наречеме графички структурирани алгебри). Покажуваме својство на универзалност на монографиите, во смисла дека сите графички структурирани алгебри можат да се претстават (иако обично не на канонски начин) како типизирани монографии, т.е. како морфизми на монографии.

Поимот структура на графиконот е воведен во [3] со цел да се добијат категории на парцијални хомоморфизми во кои би можеле да се изведат техники на алгебарско препишување на графикони. Кореспонденцијата со монографиите утврдени во Дел 6 бара сличен развој на парцијалните морфизми на монографиите во Одделот 7. Методите на еднократно и двојно истиснување на препишување монографии потоа може да се дефинираат, анализираат и споредат во Дел 8.

Поимот Е-граф е воведен во [2] со цел да се добијат добро воспитани категории (препишување на графикон за пишување) на припишаните графикони, и оттаму да се предложат соодветни претстави на структурите на податоци од реалниот живот. Ова се постигнува со збогатување на Е-графиците со алгебра од типот на податоци и со идентификување на јазли со сортирање со елементите на оваа алгебра. Следуваме сличен пристап во Дел 9 со идејата за припишана типизирана монографија со идентификување на елементи на алгебра со рабови и добиваме слично добро воспитани категории. Поради универзалноста на монографиите гледаме дека секоја Σ-алгебра може да се претстави како припишана типизирана монографија.

Заклучуваме во Дел 10. Забележете дека делови од Секциите 4 до 6 се објавени во [4].