Seminar za Logiku, Algebru, DIskretnu Matematiku i teorijsko računarstvo
Logic, Algebra, DIscrete Mathematics and Theoretical Computer Science Seminars

Zimski semestar 2018. / Autumn semester 2018

05 & 26/12/2018
Ivana Đurđev (PMF Novi Sad): Sendvič polugrupe u lokalno malim kategorijama

Neka su X i Y fiksirani, različiti, neprazni skupovi, a f,g:X→Y proizvoljne funkcije. Jasno, f i g se ne mogu direktno komponovati; međutim, ako odaberemo proizvoljno preslikavanje a:Y→ X, rezultat kompozicije fag je funkcija X→Y. Štaviše, skup svih funkcija iz X u Y, T_XY, zajedno sa operacijom definisanom sa f◦g=fag za sve f,g iz T_XY  je polugrupa. Nazivamo je sendvič polugrupa funkcija. Prirodno je zapitati se da li ista ideja funkcioniše ukoliko umesto funkcija koristimo neke druge objekte. Naravno, odgovor je potvrdan, te nam je neophodan opšti pojam koji obuhvata sve te slučajeve.

U tu svrhu definišemo sendvič polugrupu u lokalno maloj kategoriji. U predavanju sažeto izlažemo rezultate tri rada. Kombinujući njihov sadržaj, opisujemo osobine sendvič polugrupe u lokalno maloj kategoriji, a onda posmatramo i iste osobine u specijalnim slučajevima: u sendvič polugrupama funkcija (parcijalnih, "običnih" i injektivnih), i sendvič polugrupama specijalnih konstrukcija zvanih dijagrami (bitnih zbog veze sa tzv. dijagram-algebrama koje su ključne u statističkoj mehanici i teoriji reprezentacije algebarskih grupa). Osobine koje koristimo da opišemo te polugrupe su karakterizacije Grinovih relacija, klasa i njihovih odnosa, idempotenata, regularne potpolugrupe, idempotentno generisane potpolugrupe, uz rezultate vezane za pitanja generisanosti i ranga polugrupe, kao i njenih bitnih potpolugrupa.

21/11/2018
Krisztina Ágó Balog (PMF Novi Sad): O nekim reverznoinvarijantnim merama složenosti višearnih reči (On some reversal-invariant complexity measures of multiary words)

Postoje razne funkcije koje predstavljaju mere složenosti date reči. U ovom izlaganju posmatramo neke od njih koje su invarijantne u odnosu na operaciju preokretanja reči.

U prvom delu prezentacije ključnu ulogu ima tzv. palindromska složenost, pomoću koje se definiše palindromski defekt reči. Postoje mnogobrojni rezultati koje se odnose na takozvane bogate reči (reči čije je defekt 0), dok se o rečima sa konačnim pozitivnim defektom relativno malo zna. Konkretno, uz još neke prirodne restrikcije, naime aperiodičnost i zatvorenost skupa faktora za preokretanje, donedavno nije bio poznat nijedan primer takve reči. Prvi primeri koji su se pojavili u literaturi su bile tzv. visokopotencijalne reči. U ovom delu izlaganja predstavićemo daleko opštiju konstrukciju, kojom se dobija znatno šira klasa reči (nazvanih uopštene visokopotencijalne reči, budući da su visokopotencijalne reči ovde zapravo specijalan slučaj), i analiziraćemo njihov značaj u okvirima kombinatorike na rečima.

Drugi deo prezentacije je posvećen takozvanoj MP-razmeri date reči. Taj pojam je inicijalno bio definisan samo za binarne reči kao količnik dužine najkraće minimalno palindromične reči koja sadrži zadatu reč kao faktor, i dužine same zadate reči. Pritom se minimalno palindromična reč definiše kao reč koja ne sadrži palindromsku podreč dužu od polovine svoje dužine (jasno, svaka binarna reč sadrži palindromsku podreč dugačku bar toliko, što opravdava naziv). Pokazano je ranije da je u binarnom slučaju ta razmera najviše 4 i da se ova gornja granica ne može poboljšati, a ostalo je otvoreno pitanje da li se MP-razmera (tj. njen očigledan prirodan analogon) može definisati i u slučaju alfabeta neke arnosti veće od 2. U ovom delu izlaganja pokazaćemo da to jeste slučaj za ternarni alfabet, utvrdićemo da je najbolje gornje ograničenje MP-razmere u tom slučaju 6, i konstatovaćemo da se niz vrlo neintuitivnih osobina ranije uočenih u binarnom slučaju prenosi i na veću arnost.

24/10/2018 & 07/11/2018
Samir Zahirović (PMF Novi Sad): Enhanced power grafovi konačnih grupa

Enhanced power graph grupe je graf čiji skup čvorova čine elementi grupe, a u kome su dva elementa susedna ako su sadržana nekoj cikličnoj grupi. Dokazujemo da konačne grupe sa izomorfnim enhanced power grafovima imaju izomorfne usmerene power grafove. Pokazujemo da je svaki izomorfizam između power grafova takođe i izomorfizam odgovarajućih enhanced power grafova, i nalazimo sve konačne grupe čiji enhanced power grafovi imaju Abelove grupe automorfizama. Takođe nalazimo sve konačne grupe za koje je red grupe automorfizama enhanced power grafa stepen prostog broja, odnosno kvadratno slobodan. Pored ovoga, opisujemo i enhanced power grafove konačnih Abelovih grupa. Konačno, dajemo karakterizaciju konačnih nilpotentnih grupa čiji su enhanced power grafovi perfektni, i predstavljamo dovoljan uslov za slabu perfektnost enhanced power grafa konačne grupe.

24/09/2018 (ponedeljak / Monday, 12:00)
Heiko Vogler (TU Dresden, Germany): Support of recognizable weighted languages

We consider weighted string automata where the weights are taken from a  strong bimonoid K, and we consider the weighted languages (or: formal power series) computed by such automata. We recall that, in general, the support of such weighted languages is not recognizable. However, if K  is zero-sum free and zero-divisor free, then they are recognizable. Finally, we prove that recognizability also holds for each zero-sum free and commutative strong bimonoid.