Search

This thesis is a survey of some well-known and several new results concerning lattices of total, partial, incompletely specified clones and hyper-clones. We assign to every partial, incompletely specified and hyperoperation a suitable total operation and investigate thereby induced embeddings of the three lattices into corresponding lattices of total clones. Next we modify the famous Galois connection (Pol,Inv) between relations and operations for partial operations, IS operations and hyperoperations and describe classes of clones of IS operations and hyperoperations which strongly and weakly preserve given relations. We also state some known results concerning the four lattices on a two-element set. Finally, we present completeness criteria for the lattices of total and partial clones, and in the case of hyperclones and IS clones we describe four classes of coatoms, determined by four classes of Rosenberg’s relations. Ова теза представља преглед неких познатих и неколико нових резултата везаних за мреже тоталних, парцијалних, непотпуно специфицираних клонова и хиперклонова. Свакој парцијалној, непотпуно специфицираној и хипероперацији придружијемо одговарајућу тоталну операцију, и испитујемо тиме индукована потапања три мреже у одговарајуће мреже тоталних клонова. Потом познату Галоаову везу (Pol,Inv) између релација и операција модификујемо за парцијалне операције, НС опера-ције и хипероперације и описујемо класе клонова непотпуно специфици-раних и хипероперација које јако и слабо чувају дате релације. Такође наводимо неке познате резултате о мрежама на двоелементном скупу. Коначно, наводимо критеријуме комплетности за мреже тоталних и парцијалних клонова, а у случају хиперклонова и НС клонова описујемо четири класе коатома, одређених са четири класе Розенбергових релација. Ova teza predstavlja pregled nekih poznatih i nekoliko novih rezultata vezanih za mreže totalnih, parcijalnih, nepotpuno specificiranih klonova i hiperklonova. Svakoj parcijalnoj, nepotpuno specificiranoj i hiperoperaciji pridružijemo odgovarajuću totalnu operaciju, i ispitujemo time indukovana potapanja tri mreže u odgovarajuće mreže totalnih klonova. Potom poznatu Galoaovu vezu (Pol,Inv) između relacija i operacija modifikujemo za parcijalne operacije, NS opera-cije i hiperoperacije i opisujemo klase klonova nepotpuno specifici-ranih i hiperoperacija koje jako i slabo čuvaju date relacije. Takođe navodimo neke poznate rezultate o mrežama na dvoelementnom skupu. Konačno, navodimo kriterijume kompletnosti za mreže totalnih i parcijalnih klonova, a u slučaju hiperklonova i NS klonova opisujemo četiri klase koatoma, određenih sa četiri klase Rozenbergovih relacija.

This thesis is a survey of some well-known and several new results concerning lattices of total, partial, incompletely specified clones and hyper-clones. We assign to every partial, incompletely specified and hyperoperation a suitable total operation and investigate thereby induced embeddings of the three lattices into corresponding lattices of total clones. Next we modify the famous Galois connection (Pol,Inv) between relations and operations for partial operations, IS operations and hyperoperations and describe classes of clones of IS operations and hyperoperations which strongly and weakly preserve given relations. We also state some known results concerning the four lattices on a two-element set. Finally, we present completeness criteria for the lattices of total and partial clones, and in the case of hyperclones and IS clones we describe four classes of coatoms, determined by four classes of Rosenberg’s relations., Ова теза представља преглед неких познатих и неколико нових резултата везаних за мреже тоталних, парцијалних, непотпуно специфицираних клонова и хиперклонова. Свакој парцијалној, непотпуно специфицираној и хипероперацији придружијемо одговарајућу тоталну операцију, и испитујемо тиме индукована потапања три мреже у одговарајуће мреже тоталних клонова. Потом познату Галоаову везу (Pol,Inv) између релација и операција модификујемо за парцијалне операције, НС опера-ције и хипероперације и описујемо класе клонова непотпуно специфици-раних и хипероперација које јако и слабо чувају дате релације. Такође наводимо неке познате резултате о мрежама на двоелементном скупу. Коначно, наводимо критеријуме комплетности за мреже тоталних и парцијалних клонова, а у случају хиперклонова и НС клонова описујемо четири класе коатома, одређених са четири класе Розенбергових релација., Ova teza predstavlja pregled nekih poznatih i nekoliko novih rezultata vezanih za mreže totalnih, parcijalnih, nepotpuno specificiranih klonova i hiperklonova. Svakoj parcijalnoj, nepotpuno specificiranoj i hiperoperaciji pridružijemo odgovarajuću totalnu operaciju, i ispitujemo time indukovana potapanja tri mreže u odgovarajuće mreže totalnih klonova. Potom poznatu Galoaovu vezu (Pol,Inv) između relacija i operacija modifikujemo za parcijalne operacije, NS opera-cije i hiperoperacije i opisujemo klase klonova nepotpuno specifici-ranih i hiperoperacija koje jako i slabo čuvaju date relacije. Takođe navodimo neke poznate rezultate o mrežama na dvoelementnom skupu. Konačno, navodimo kriterijume kompletnosti za mreže totalnih i parcijalnih klonova, a u slučaju hiperklonova i NS klonova opisujemo četiri klase koatoma, određenih sa četiri klase Rozenbergovih relacija.

U ovoj tezi opisujemo linearne, idempotentne, jake Maljcevljeve uslove za kongruencijsku ^-poludistributivnost u lokalno konačnim varijetetima. U [40] je predstavljen jedan takav jak Maljcevljev uslov i tehnika koju su autori koristili je uopštenje jednog od glavnih rezultata iz [46]. Glavna razlika je u tome što jednostavna primjena Dirihleovog principa u [46] postaje dosta komplikovaniji argument Remzijevskog tipa u [40]. Mi ovdje dodatno uopštavamo taj argument i prezentujemo dokaz pomenute karakterizacije. Svi ovi radovi koriste snažan rezultat [4] L. Barta o rješivosti Problema zadovoljenja uslova metodama provjere lokalne konzistencije uslova, pa je treća glava teze posvećena detaljnoj prezentaciji tog rada. Takođe, dokazujemo da neki jak Maljcevljev uslov karakteriše kongruencijsku ^-poludistributivnost u lokalno konačnim varijetetima ako i samo ako je realizovan u određenoj četvoroelementnoj algebri. Na kraju, bavimo se i problemom pronalaženja optimalnog jakog Maljcevljevog uslova koji karakteriše egzistenciju Tejlorovog terma u opštem slučaju. U [53] M. Olšak predstavio je iznenađujući rezultat da je egzistencija Tejlorovog terma jako Maljcevljevo svojstvo. Term iz prvobitne verzije [53] ima arnost 12, dok mi ovdje prezentujemo dokaz da se arnost može redukovati na 9., In this thesis we describe linear, idempotent, strong Mal’cev conditions for congruence ^-semidistributivity in locally finite varieties. In [40] authors presented one such Mal’cev condition and technique they used is generalization of one result from [46]. Main difference is that simple application of Pigeonhole prinicple from [46] becomes much more complicated Ramsey style argument in [40]. Here we dditionaly generalize that argument and we present the proof of above mentioned characterization. All these papers use deep result [4] by L. Barto on solvability of Constraint Satisfaction Problem by local consistency checking methods, so third chapter of this thesis is dedicated to detailed presentation of [4]. Also, we prove that some strong Mal’cev condition characterizes congruence ^-semidistributivity in locally finite varieties if and only if it is realized in certain four element algebra. Finally, we work on the problem of finding optimal strong Mal’cev condition for existence of Taylor term in general case. In [53] M. Olsak presented suprising result that exisstence of Taylor term is strong Malcev property. The term from first version of [53] has arity 12, but here we prove that arity can be reduced to 9.

Let S be a locally small category, and fix two (not necessarily distinct) objectsi, j in S. Let Sij and Sji denote the set of all morphisms i → j and j → i, respectively. Fixa ∈ Sji and define (Sij , ? a), where x?a y = xay for x, y ∈ Sij . Then, (Sij , ? a ) is a semigroup, known as a sandwich semigroup, and denoted by S a ij . In this thesis, we conduct a thorough investigation of sandwich semigroups (in locally small categories) in general, and then apply these results to infer detailed descriptions of sandwich semigroups in a number of categories. Firstly, we introduce the notion of a partial semigroup, and establish a framework for describing a category in "semigroup language". Then, we prove various results describing Green’s relations and preorders, stability and regularity of S a ij . In particular, we emphasize the relationships between the properties of the sandwich semigroup and the properties of the category containing it. Also, we highlight the significance of the properties of the sandwich element a. In this process, we determine a natural condition on a called sandwich regularity which guarantees that the regular elements of S a ij form a subsemigroup tightly connected tocertain non-sandwich semigroups. We explore these connections in detail and infer major structural results on Reg(S a ij) and the generation mechanisms in it. Finally, we investigate ranks and idempotent ranks of the regular subsemigroup Reg(S a ij ) and idempotent-generated subsemigroup E(S a ij ) of S a ij . In general, we are able to infer expressions for lower bounds for these values. However, we show that in the case when Reg(S a ij ) is MI-dominated (a property which has to do with the "covering power" of certain local monoids), the mentioned lower bounds are sharp. We apply the general theory to sandwich semigroups in various transformation categories (partial maps P T , injective maps I , totally defined maps T , and matrices M(F) − corresponding to linear transformations of vector spaces over a field F) and diagram categories (partition P , lanar partition PP , Brauer B, partial Brauer PB, Motzkin M , and Temperley-Lieb T L categories), one at a time. In each case, we investigate the partial semigroup itself in terms of Green’s relations and regularity and then focus on a sandwich semigroup in it. We apply the general results to thoroughly describe its structural and combinatorial properties. Furthermore, since in each category that we consider all elements are sandwich-regular, we may apply the theory concerning the regular subsemigroup in allof these cases. In particular, Reg(S a ij ) turns out to be tightly connected to a certain nonsandwich monoid for each category S we consider, and we are able to describe eg(S a ij ) and E(S a ij ). However, we conduct the combinatorial part of the investigation only for the sandwich semigroups in transformation categories (P T , I , T , and M(F)) and sandwich semigroups in the Brauer category B since only these have MI-dominated regular subsemigroups (and some other properties that make them more amenable to investigation). For these sandwich semigroups, we enumerate regular Green’s classes and idempotents, and we calculate the ranks (and idempotent ranks, where appropriate) of Reg(S a ij ), E(S a ij ) and S a ij ., Neka je S lokalno mala kategorija. Fiksirajmo proizvoljne (ne nužno različite) objekte i i j iz S. Neka Sij i Sji označavaju skupove svih morfizama i → j i j → i, redom. Fiksirajmo morfizam a ∈ Sji i definišimo strukturu (Sij , ? a ), gde je x ? a y = xay za sve x, y ∈ Sij . Tada je (Sij , ? a ) sendvič polugrupa, koju označavamo sa S a ij . U tezi ćemo sprovesti detaljno ispitivanje sendvič polugrupa (u lokalno maloj kategoriji) u opštem slučaju, a zatim ćemo primeniti dobijene rezultate u cilju opisivanja sendvič polugrupa u konkretnim kategorijama. Najpre uvodimo pojam parcijalne polugrupe i postavljamo osnovu koja nam omogu-ćava da opišemo kategoriju na "jeziku polugrupa". Zatim slede brojni rezultati koji opisuju Grinove relacije i poretke, kao i stabilnost i regularnost polugrupe (Sij , ? a ). Tu posebno ističemo veze između osobina sendvič polugrupe i parcijalne polugrupe koja je sadrži. Takođe, posebnu pažnju posvećujemo uticaju sendvič elementa a na osobine sendvič polugrupe (Sij , ? a ). Kao najbitniji primer se izdvaja osobina sendvič-regularnosti ; naime, dokazujemo da, ako je a sendvič- regularan, onda regularni elementi iz S a ij formiraju podgrupu koja je usko povezana sa određenim "ne-sendvič" polugrupama. U tezi detaljno ispitujemo te veze i dobijamo važne rezultate o strukturi polugrupe Reg(Sij , ? a ) i mehanizmima generisanja u njoj. Za kraj, ispitujemo rangove i idempotentne rangove regularne potpolugrupe Reg(Sij , ? a ) i idempotentno-generisane potpolugrupe E(Sij , ? a ). U opštem slučaju možemo dati donja ograničenja za ove vrednosti. Međutim, u slučaju kada je regularna polugrupa Reg(Sij , ? a ) MI-dominirana (što znači da je određeni lokalni monoidi pokrivaju), ta donja ograničenja su dostignuta. U ostatku teze, primenjujemo opštu teoriju na sendvič polugrupe u brojnim kategorijama transformacija (parcijalne funkcije P T , injektivne parcijalne funkcije I , potpuno definisane funkcije T i matrice M(F), koje predstavljaju linearne transformacije vektorskih prostora nad poljem F) i kategorijama dijagrama (particije P , planarne particije PP , Brauerove B,parcijalne Brauerove PB, Mockinove M , i Temperli-Lib T L particije). U svakom od ovih slučajeva, prvo istražujemo parcijalnu polugrupu iz aspekta Grinovih relacija i regularnosti, a zatim se fokusiramo na (proizvoljnu) sendvič polugrupu u njoj. Pri tome, primenjujemo opšte rezultate da bismo detaljno opisali njenu strukturu i kombinatorne osobine. Osim toga, u svim slučajevima primenjujemo i teoriju vezanu za regularnu potpolugrupu, pošto su svi elementi u našim kategorijama sendvič-regularni. To znači da je u svakoj kategoriji S koju razmatramo, Reg(Sij , ? a ) usko povezana sa određenim monoidom, i preko te veze možemo opisati polugrupe Reg(Sij , ? a ) i E(Sij , ? a ). Ipak, kombinatorni deo ispitivanja sprovodimo samo za sendvič polugrupe u kategorijama transformacija (P T , I , T i M(F)) i sendvič polugrupe u Brauerovoj kategoriji B, pošto samo one imaju MI-dominirane regularne potpolugrupe (i još neke osobine koje ih čine pogodnijim za ispitivanje). U ovim sendvič polugrupama računamo broj regularnih Grinovih klasa i idempotenata, i izračunavamo rangove (i idempotentne rangove, ako postoje) polugrupa Reg(Sij , ? a ), E(Sij , ? a ) i S a ij .

Ako je L relacijski jezik, kondenzacioni pretporedak na skupu IntL (X) svih L-interpretacija nad domenom X, dat je sa: ρ≼c σ ako postoji bijektivni homomorfizam (kondenzacija) f:〈X,ρ〉→〈X,σ〉. Odgovarajući antisimetrični količnik 〈Int L (X)/~c,≤c〉 ~naziva se kondenzacioni poredak. Za proizvoljnu L-interpretaciju ρ, klasa [ρ]~c je konveksno zatvorenje klase [ρ]_≅ u Booleovoj mreži 〈IntL (X),⊆〉. Za L-interpretaciju ρ reći ćemo da je jako reverzibilna (redom, reverzibilna, slabo reverzibilna) akko je klasa [ρ]_≅ (ili, ekvivalentno, klasa [ρ]~c )) singlton (redom, antilanac, konveksan skup) u Booleovoj mreži 〈IntL (X),⊆〉. U cilju ispitivanja poseta 〈Int(Lb ) (X)/~c,≤c〉, za ρ∈IrreflX uveden je skup Dρ:={[ρ∪ΔA ](~c ):A⊆X} i pokazano je kako je poduređenje 〈Dρ,≤c 〉 izomorfno određenom količniku partitivnog skupa P(X). Fenomen reverzibilnosti relacijskih struktura igra istaknutu ulogu u istraživanju tog poduređenja. U slučaju prebrojivog jezika L i prebrojivog domena X, pokazano je da su ~c i [ρ]~c analitički skupovi u poljskim prostorima, redom, IntL (ω)×IntL (ω) i IntL (ω), i pomoću toga, pokazano ja da su, u slučaju prebrojivog jezika i domena, klase [ρ]≅ i [ρ]~c iste veličine, i da je to neki kardinal iz {1,ω,c}. Dalje je istražena hijerarhija između kondenzacione ekvivalencije, elementarne ekvivalencije, ekvimorfizma (bi-utopivosti) i drugih sličnosti L-struktura određenih nekim sličnostima njihovih monoida samoutapanja. Naposletku, temeljno je istražen fenomen reverzibilnosti L-struktura. Data je karakterizacija jako reverzibilnih L-intepretacija kao onih čije su komponentne relacije definabilne formulama praznog jezika L∅, bez kvantifikatora i parametara. Pokazano je kako su slabo reverzibilne interpretacije upravo one koje imaju svojstvo Cantor-Schrӧder-Bernstein (kraće, svojstvo CSB) za kondenzacije. Poseban naglasak stavljen je na detektovanje relevantnih klasa reverzibilnih struktura. Pri tome, prvo su proučene strukture koje su ekstremni elementi L∞ω-definabilnih klasa interpretacija, pri određenim sintaktičkim ograničenjima, a zatim su istražene nepovezane Lb-strukture, gde je dato nekoliko karakterizacija njihove reverzibilnosti. If L is a relational language, the condensational preorder on the set IntL (X) of all L-interpretations over the domain X, is given with: ρ≼_c σ iff there exists a bijective homomorphism (condensation) f:〈X,ρ〉→〈X,σ〉. The corresponding antisymmetric quotient 〈IntL (X)/~c,≤_c〉 will be called the condensational order. For any L-interpretation ρ, the class [ρ]~c ) is the convex closure of the class [ρ]≅ in the Boolean lattice 〈IntL (X),⊆〉. An L-interpretation ρ is said to be strongly reversible (respectively, reversible, weakly reversible) iff the class [ρ]≅ (or, equivalently, the class [ρ]~c )) is a singleton (respectively, an antichain, a convex set) in the poset 〈 IntL (X),⊆〉. In order to investigate the poset 〈Int(Lb ) (X)/~c,≤_c〉, for ρ∈ IrreflX the following set is defined Dρ:={[ρ∪ΔA ]_~c :A⊆X}. It is shown that the suborder 〈Dρ,≤c 〉 is isomorphic to a certain quotient of the power set P(X). The phenomenon of reversibility plays prominent role in the investigation of that suborder. In the case of a countable language L and a countable domain X, it is shown that ~c and [ρ]_~c are analytic sets in the Polish spaces, respectively, IntL (ω)× IntL (ω) and IntL (ω), and, using those results, in the case of a countable language and domain it is shown that the classes [ρ]_≅ and [ρ]~c are of the same size, and that it is a cardinals from {1,ω,c}. Next, the hierarchy between condensational equivalence, elementary equivalence, equimorphism (bi- embedability) and other similarities of L-structures, determined by some similarities of their self-embedding monoids, is investigated. In the last part, the phenomenon of reversibility of L-structures is investigated. Strongly reversible L-intepretations are characterized as those whose component relations are definable by the formulae of the empty language L∅, without quantifiers and parameters. It is shown that weakly reversible interpretations are exactly those having the property Cantor-Schrӧder-Bernstein (shorter, the property CSB) for condensations. Particular emphasis is put on detecting relevant classes of reversible structures. First, the structures that are extreme elements of L∞ω-definable classes of interpretations, under certain syntactical restrictions, are investigated. Following that, disconnected Lb-structures are investigated, where several equivalents of their reversibility are proven.

U radu je ispitan sledeći problem: Pod kojimuslovima se može rekonstruisati (sintetisati)intervalno-vrednosni rasplinuti skup iz poznatefamilije nivo skupova.U tu svrhu su proučena svojstva mrežaintervala za svaki od četiri izabrana mrežnauređenja: poredak po komponentama, neprecizniporedak (skupovna inkluzija), strogi i leksikografskiporedak.Definisane su i-između i ili-između ravnemreže i ispitana njihova svojstva potrebna zarešavanje postavljenog problema sinteze zaintervalno-vrednosne rasplinute skupove. Za i-između ravne mreže je dokazano da su, u svomkonačnom slučaju, slim mreže i dualno, da su ili-između ravne mreže dualno-slim mreže.Data je karakterizacija kompletnih konačnoprostornih i dualno konačno prostornih mreža.Određena je klasa mreža koje se moguinjektivno preslikati u direktan proizvod nkompletnih lanaca tako da su očuvani supremumi idualno, određena je klasa mreža koje se moguinjektivno preslikati u direktan proizvod n lanacatako da su očuvani infimumi.U rešavanju problema sinteze posmatrana sudva tipa nivo skupova - gornji i donji nivo skupovi.Potreban i dovoljan uslov za sintezu intervalno-vrednosnog rasplinutog skupa iz poznate familijenivo skupova određen je za mrežu intervala koja jeuređena poretkom po komponentama, za oba tipaposmatranih nivo skupova.Za mrežu intervala uređenu nepreciznimporetkom, problem je rešen za donje nivo skupove,dok su za gornje nivo skupove određeni dovoljniuslovi.Za mrežu intervala koja je uređenaleksikografskim poretkom, takođe su dati dovoljniuslovi i to za oba tipa nivo skupova.Za mrežu intervala uređenu strogim poretkomproblem nije rešavan, jer izlazi izvan okvira ovograda.Dobijeni rezultati su primenjeni za rešavanjesličnog problema sinteze za intervalno-vrednosneintuicionističke rasplinute skupove za mrežuintervala uređenu poretkom po komponentama.Rezultati ovog istraživanja su od teorijskogznačaja u teoriji mreža i teoriji rasplinutih skupova,ali postoji mogućnost za primenu u matematičkojmorfologiji i obradi slika., In this thesis the following problem was investigated: Under which conditions an interval-valued fuzzy set can be reconstructed from the given family of cut sets.We consider interval-valued fuzzy sets as a special type of lattice-valued fuzzy sets and we studied properties of lattices of intervals using four different lattice order: componentwise ordering, imprecision ordering (inclusion of sets), strong andlexicographical ordering.We proposed new definitions of meet-between planar and join - between planar lattices, we investigated their properties and used them for solving problem of synthesis in interval-valued fuzzy sets.It has been proven that finite meet- between planar lattices and slim lattices are equivalent, and dually: finite join- between planar lattices and dually slim lattices are equivalent.Complete finitely spatial lattices and complete dually finitely spatial lattices are fullycharacterized in this setting. Next, we characterized lattices which can be orderembedded into a Cartesian product of n complete chains such that all suprema are preserved under the embedding.And dually, we characterized lattices which can be order embedded into a Cartesian product of n complete chains such that all infima are preserved under the embedding.We considered two types of cut sets – upper cuts and lower cuts.Solution of the problem of synthesis of interval-valued fuzzy sets are given for lattices of intervals under componentwise ordering for both types of cut sets. Solution of problem of synthesis of interval-valued fuzzy sets are given for lower cuts for lattices of intervals under imprecision ordering. Sufficient conditions are given for lattices of intervals under imprecision ordering and family of upper cuts.Sufficient conditions are also given for lattices of intervals under lexicographical ordering.The problem of synthesis of interval-valued fuzzy sets for lattices of intervals under strong ordering is beyond the scope of this thesis.A similar problem of synthesis of interval-valued intuitionistic fuzzy sets is solved for lattices of intervals under componentwise ordering.These results are mostly of theoretical importance in lattice theory and fuzzy sets theory, but also they could be applied in mathematical morphology and in image processing.

U radu je ispitan sledeći problem: Pod kojim uslovima se može rekonstruisati (sintetisati) intervalno-vrednosni rasplinuti skup iz poznate familije nivo skupova. U tu svrhu su proučena svojstva mreža intervala za svaki od četiri izabrana mrežna uređenja: poredak po komponentama, neprecizni poredak (skupovna inkluzija), strogi i leksikografski poredak. Definisane su i-između i ili-između ravne mreže i ispitana njihova svojstva potrebna za rešavanje postavljenog problema sinteze za intervalno-vrednosne rasplinute skupove. Za i-između ravne mreže je dokazano da su, u svom konačnom slučaju, slim mreže i dualno, da su ili-između ravne mreže dualno-slim mreže. Data je karakterizacija kompletnih konačno prostornih i dualno konačno prostornih mreža. Određena je klasa mreža koje se mogu injektivno preslikati u direktan proizvod n kompletnih lanaca tako da su očuvani supremumi i dualno, određena je klasa mreža koje se mogu injektivno preslikati u direktan proizvod n lanaca tako da su očuvani infimumi. U rešavanju problema sinteze posmatrana su dva tipa nivo skupova - gornji i donji nivo skupovi. Potreban i dovoljan uslov za sintezu intervalno-vrednosnog rasplinutog skupa iz poznate familije nivo skupova određen je za mrežu intervala koja je uređena poretkom po komponentama, za oba tipa posmatranih nivo skupova. Za mrežu intervala uređenu nepreciznim poretkom, problem je rešen za donje nivo skupove, dok su za gornje nivo skupove određeni dovoljni uslovi. Za mrežu intervala koja je uređena leksikografskim poretkom, takođe su dati dovoljni uslovi i to za oba tipa nivo skupova. Za mrežu intervala uređenu strogim poretkom problem nije rešavan, jer izlazi izvan okvira ovog rada. Dobijeni rezultati su primenjeni za rešavanje sličnog problema sinteze za intervalno-vrednosne intuicionističke rasplinute skupove za mrežu intervala uređenu poretkom po komponentama. Rezultati ovog istraživanja su od teorijskog značaja u teoriji mreža i teoriji rasplinutih skupova, ali postoji mogućnost za primenu u matematičkoj morfologiji i obradi slika. In this thesis the following problem was investigated: Under which conditions an interval-valued fuzzy set can be reconstructed from the given family of cut sets. We consider interval-valued fuzzy sets as a special type of lattice-valued fuzzy sets and we studied properties of lattices of intervals using four different lattice order: componentwise ordering, imprecision ordering (inclusion of sets), strong and lexicographical ordering. We proposed new definitions of meet-between planar and join - between planar lattices, we investigated their properties and used them for solving problem of synthesis in interval-valued fuzzy sets. It has been proven that finite meet- between planar lattices and slim lattices are equivalent, and dually: finite join- between planar lattices and dually slim lattices are equivalent. Complete finitely spatial lattices and complete dually finitely spatial lattices are fully characterized in this setting. Next, we characterized lattices which can be order embedded into a Cartesian product of n complete chains such that all suprema are preserved under the embedding. And dually, we characterized lattices which can be order embedded into a Cartesian product of n complete chains such that all infima are preserved under the embedding. We considered two types of cut sets – upper cuts and lower cuts. Solution of the problem of synthesis of interval-valued fuzzy sets are given for lattices of intervals under componentwise ordering for both types of cut sets. Solution of problem of synthesis of interval-valued fuzzy sets are given for lower cuts for lattices of intervals under imprecision ordering. Sufficient conditions are given for lattices of intervals under imprecision ordering and family of upper cuts. Sufficient conditions are also given for lattices of intervals under lexicographical ordering. The problem of synthesis of interval-valued fuzzy sets for lattices of intervals under strong ordering is beyond the scope of this thesis. A similar problem of synthesis of interval-valued intuitionistic fuzzy sets is solved for lattices of intervals under componentwise ordering. These results are mostly of theoretical importance in lattice theory and fuzzy sets theory, but also they could be applied in mathematical morphology and in image processing.

Ova teza se bavi ¤-kvazilinearnim varijetetima grupoida. Pokazano je da postoji ta·cno dvadeset osam idempotentnih ¤-kvazilinearnih varijeteta grupoida, od kojih dvadeset ·sest varijeteta imaju kona·cnu bazu i te baze su i navedene, dok preostala dva varijeteta imaju inherentno beskona·cnu bazu. U tezi je opisano ured enje svih idempotentnih ¤-kvazilinearnih varijeteta grupoida i nalazimo male grupoide koji generi·su svaki od navedenih varijeteta. Na kraju je pokazano da postoji kontinum mnogo ¤-kvazilinearnih variejeteta grupoida., The topic of this thesis are ¤-quasilinear varieties of groupoids.We show that there exist exactly twenty-eight idempotent ¤-quasilinear varieties of groupoids, twenty-six of which are ¯nitely based (and we explicitlygive ¯nite bases for each of them), while two are inherently non¯nitely based.We describe the ordering of these twenty-eight idempotent ¤-quasilinear varieties of groupoids and ¯nd small generating algebras for each of them. Inthe end we show that there exist continuum many ¤-quasilinear varieties ofgroupoids, not all of which are even locally ¯nite.

Ovaj rad se bavi algebrama kompleksa i stepenim konstukcijama uopste. Prvo poglavlje sadrzi pregled poznatih rezultata iz ove oblasti. U drugom poglavlju razmatrani su neki univerzalno-algebarski problemi vezani za algebre kompleksa, koji su pokrenuti u radovima C. Brinka. Trece poglavlje sadr ´ zi rezultate o stepenim grafovima, sa posebnim osvrtom na globalnu odredjenost grafova., The thesis deals with power algebras and power constructions in general. The first chapter contains the most important known results from this field. In Chapter 2 some universal-algebraic problems concerning power algebras are considered. Chapter 3 is devoted to the investigation of power graphs. The main attention is focused on the problem of global determinism of graphs.&nbsp

Jezik nad E je proizvoljan skup reci nad E, tj. proizvoljan podskup slobodnog monoida E*. Jezici nad datom azbukom formiraju al­ gebre jezika, sa operacijama unije, konkatenacije (dopisivanja red), Kleene-jeve iteracije i sa 0, {A} kao konstantama. Regularni jezici nad E su elementi podalgebre algebre jezika nad E generisane konačnim jezicima. Ispostavlja se da algebre jezika generišu isti varijetet (i stoga zadovoljavaju iste iden­titete) kao i algebre binarnih relacija snabdevene operacijama unije, kompozi­cije, refleksivno-tranzitivnog zatvorenja i praznom relacijom i dijagonalom kao konstantama. Reč je o varijetetu Kleenejevih algebri, i slobodne algebre tog varijeteta su baš algebre regularnih jezika. Na početku disertacije, izloženi su neki aspekti algebarske teorije automata i formalnih jezika, teorije binarnih relacija i univerzalne algebre, relevantni za ispitivanje identiteta na algebrama jezika. Zatim je dat klasični rezultat (Redko, 1964.) da varijetet Kleenejevih algebri nema konačnu bazu identiteta. Ovde je prikazan dokaz Conwaya iz 1971., budući da on sadrži neke ideje koje su se pokazale korisne za dalji rad. Glave 3 i 4 sadrže originalne rezultate usmerene na profinjenje Redkovog rezultata. Pokazano je da uzroci beskonačnosti baze identiteta za Kleenejeve algebre leže u interakciji operacija konkatenacije i iteracije jezika (odnosno, kompozicije i refleksivno-tranzitivnog zatvorenja relacija). Drugim recima, klasa redukata algebri jezika bez operacije unije nema konačnu bazu identiteta. To daje odgovor na problem D. A. Bredikhina iz 1993. godine. S druge strane, proširenjem tipa Kleenejevih algebri involutivnom operacijom inverza jezika, odnosno relacija, takođe se dolazi do beskonačno baziranih varijeteta, čime se rešava problem B. Jonssona iz 1988. godine. Analogno, komutativni jezici nad E su proizvoljni podskupovi slobodnog komutativnog monoida E®. U Glavi 5 je dokazano da se jednakosna teorija algebri komutativnih jezika poklapa sa jednakosnom teorijom algebre (regu­larnih) jezika nad jednoelementnim alfabetom, što daje odgovor na problem koji je još 1969. formulisao A. Salomaa u svojoj monografiji Theory of Au­tomata.Na taj način, iz poznatih rezultata o jednakosnoj aksiomatizaciji komutativnih jezika se dobija jedna baza za algebre jezika nad jednoelement­nim alfabetom, kao i veoma kratak dokaz poznate činjenice (takođe Redko, 1964.) da algebre komutativnih jezika nemaju konačnu bazu identiteta. Na kraju disertacije, identiteti Kleenejevih algebri se posmatraju u kon­tekstu dinamičkih algebri. Reč je o algebarskoj verziji dinamičkih logika, koje su konstruisane sedamdesetih godina kao matematički model rada računara, kada se na njima izvršava program pisan u nekom imperativnom program­ skom jeziku. Na primer, problemi verifikacije i ekvivalentnosti programa se lako izražavaju preko identiteta dinamičkih algebri, tako da razne njihove jednakosne osobine odgovaraju pojmovima iz teorijskog računarstva. Takođe, interesatno je da je jednakosna teorija Kleenejevih algebri ’’ kodirana” u konačno baziranoj jednakosnoj teoriji dinamičih algebri. Polazeći od poznatih rezul­tata za dvosortne dinamičke algebre (pri čemu je jedna komponenta algebra istog tipa kao i Kleenejeve algebre, dok je druga Booleova algebra), neki od tih rezultata su transformisani i prošireni za Jonssonove dinamičke algebre (jednosortne modele dinamičkih logika). Na primer, ako se Kleenejeva algebra K može predstaviti kao konačan direktan proizvod slobodnih algebri varijeteta Kleenejevih algebri generisanih Kleenejevim relacionim algebrama, tada vari­jetet K-dinamičkih algebri ima odlučivu jednakosnu teoriju. Odavde se izvodi da svaki varijetet Kleenejevih algebri generisan Kleenejevim relacionim algeb­rama takođe ima odlučivu jednakosnu teoriju., A language over £ is an arbitrary set of words, i.e. any subset of the free monoid £*. All languages over a given alphabet form the algebra of languages, which is equipped with the operations of union, concate­nation, Kleene iteration and 0, {A } as constants. Regular languages over £ are the elements of the subalgebra of the algebra of languages over £ generated by finite languages. It turns out that algebras of languages generate exactly the same variety as algebras of binary relations, endowed with union, rela­tion composition, formation of the refelxive-transitive closure and the empty relation and the diagonal as constants. The variety in question is the vari­ety of Kleene algebras, and the algebras of regular languages are just its free algebras. The present dissertation starts with several aspects of algebraic theory of automata and formal languages, theory of binary relations and universal alge­bra, which are related to problems concerning identities of language algebras. This material is followed by the classical result (Redko, 1964) claiming that the variety of Kleene algebras have no finite equational base. We present the proof of Conway from 1971, since it contains some ideas which can be used for generalizations in different directions. Chapters 3 and 4 contain original results which refine the one of Redko. It is shown that the cause of nonfinite axiomatizability of Kleene algebras lies in the superposition of the concatenation and the iteration of languages, that is, composition of relations and reflexive-transitive closure. In other words, the class of -(--free reducts of algebras of languages has no finite equational base, which answers in the negative a problem of D. A. Bredikhin from 1993. On the other hand, by extending the type of Kleene algebras by the involutive operation of inverse of languages (converse of relations), we also obtain a nonfinitely based variety, which solves a problem of B. Jonsson from 1988. Analogously, commutative languages over E are defined as subsets of the free commutative monoid £®. It is proved in Chapter 5 that equational the­ ories of algebras of commutative languages and, respectively, of the algebra of (regular) languages over the one-element alphabet, coincide. This result settles a thirty year old problem of A. Salomaa, formulated back in his wellknown monograph Theory of Automata.Thus, we obtain an equational base for the algebra of one-letter languages, and, on the other hand, a very short proof of another Redko’s result from 1964, according to which there is no finite equational base for algebras of commutative languages. Finally, identities of Kleene algebras are considered in the context of dy­namic algebras, which are just algebraic counterparts of dynamic logics. They were discovered in the seventies as a result of the quest for an appropriate logic for reasoning about computer programs written in an imperative pro­ gramming language. For example, problems concerning program verification and equivalence can be easily translated into identities of dynamic algebras, so that many of their equational properties correspond to notions from computer science. It is also interesting that the whole equational theory of Kleene alge­ bras is ’’encoded” in the finitely based equational theory of dynamic algebras.Starting with known results on two-sorted dynamic algebras (where one com­ ponent is an algebra of the same signature as Kleene algebras, while the other is a Boolean algebra), some of those results are transformed and extended for Jonsson dynamic algebras (that is, one-sorted models of dynamic logics). For example, if a Kleene algebra K can be represented as a finite direct product of free algebras of varieties of Kleene algebras generated by Kleene relation algebras, then the variety of K-dynamic algebras has a decidable equational theory. The latter yields that all varieties of Kleene algebras generated by Kleene relation algebras have decidable equational theories, too.