Seminar for Mathematical Logic
PROGRAM
Plan rada Seminara za logiku za novembar 2015.
Seminar za matematicku logiku Matematickog instituta SANU nastavlja rad u letnjem semestru 2011/2012.g. na ovoj adresi: Kneza Mihaila 36/III sprat, soba 301f - sala za seminare. Cetvrtkom posle podne, ali od 15:00 sati, odrzavace se predavanja na Seminaru iz verovatnosnih logika pod rukovodstvom Profesora Miodraga Raskovica koji je u decembru 2007. dobio akreditaciju Naucnog veca Instituta. Na taj nacin, ponovo, kao pre vise decenija, postoje dva logicka seminara.
PETAK, 6.11.2015. U 16:15 (MI SANU, 301f)
Slavko Moconja, Matematicki fakultet Beograd
LINEARNA UREDJENJA, III deo
Rezime prvog predavanja iz ciklusa: U prvom iz serije predavanja o modelsko teorijskim osobinama linearnih uredjenja bice dat istorijski osvrt na tu oblast i najavljen sadrzaj ostalih predavanja. Cilj serije je predstavljanje par elementarnih rezultata iz disertacija Slavka Moconje i Dejana Ilica.
PETAK, 13.11.2015. U 16:15 (MI SANU, 301f)
Slavko Moconja, Matematicki fakultet Beograd
LINEARNA UREDJENJA, IV deo
PETAK, 20.11.2015. U 16:15 (MI SANU, 301f)
Slavko Moconja, Matematicki fakultet Beograd
LINEARNA UREDJENJA, V DEO
PETAK, 27.11.2015. U 16:15 (MI SANU, 301f)
Petar Markovic, PMF Novi Sad
KVANTIFIKOVANI PROBLEM ZADOVOLJENJA USLOVA PREKO POLIMORFIZAMA
Rezime: Kvantifikovani problem zadovoljenja uslova (QCSP) je problem odlucivosti sledece vrste: fiksira se jedan konacan model A na konacnom relacijskom jeziku. Ulaz problema je recenica (zatvorena formula), a problem odlucuje da li je ta recenica tacna u fiksiranom modelu. Konkretno, za QCSP se koriste recenice prvog reda u preneksnoj formi u kojima je nekvantifikovani deo samo konjunkcija atomskih formula. U prvom delu predavanja dace se pregled pocetnih rezultata na temu slozenosti QCSP, autora H. Chena, a zatim i najnovijeg (2015) sjajnog rada B. Martina i D. Zhuka. Konacno objasnice se pristup problemu preko sirjektivnih kompatibilnih operacija (sirjektivnih polimorfizama) koji su dokazali F. Bner i dr. Drugi deo predavanja posvecen je primeni tog pristiupa na klasifikaciju slozenosti QCSP kad je fiksirana struktura semikompletan digraf (usmeren graf bez petlji u kojem izmedju svaka dva razlicita cvora postoji bar jedna usmerena grana). Ilustrovacemo nase tehnike dokazivanjem jedne kljucne leme. Naime, dokazacemo da je QCSP Pspace-kompletan kad je fiksitrana struktura digraf sa 5 cvorova koji obelezavamo sa $K_{2\rightarrow 2}^{+}$. Rezultati u drugom delu su svi dokazani u radu B. Martina, P. DJapica i predavaca. Konacno, ako bude vremena, pokazacemo neke pravce za uopstenje ovih tehnika na druge strukture sem semikompletnih digrafa.
OBAVESTENJA:
Ukoliko zelite mesecne programe ovog Seminara u elektronskom obliku, obratite se: zpetric@mi.sanu.ac.rs ili tane@mi.sanu.ac.rs. Programi svih seminara Matematickog instituta SANU nalaze se na sajtu: www.mi.sanu.ac.rs
Beograd,
Srdacan pozdrav,
rukovodioci seminara Zoran Petric i Predrag Tanovic