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