Seminar for Mathematical Logic

 

PROGRAM Seminara za logiku za decembar 2008.

Posto je Matematicki institut SANU iz zgrade SANU preseljen u zgradu preko puta, Seminar za matematicku logiku Matematickog instituta SANU nastavlja rad u letnjem semestru 2007/2008. na novoj adresi: Kneza Mihaila 36/III sprat, soba 305 - Biblioteka instituta, jer zasad sala II na I spratu nove adrese nije u funkciji. U terminu Seminara, u petak, 22. i petak 29. februara 2008. posle podne, ali od 15:15 sati, gostovace prateci Seminar 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, 05.12.2008. U 14:00 SATI
Sergei Soloviev (IRIT, Toulouse, France)
Non-maximality of the theory of Symmetric Monoidal Closed Categories and dependency of categorical diagrams

Some time ago we (L. Mehats, M. Spivakovsky, S. Soloviev) had shown that there exists diagram of canonical natural transformations in SMCC such that this diagram is commutative while the classical diagram of "triple dual" is still non-commutative in some model, i.e., there exists a non-trivial extension of the theory of SMCC (the theory is non-maximal, as opposed to the case of Cartesian Closed Categories studied by Dosen and Petric). Now in our recent work with Antoine El Khoury we obtained an infinite series of diagrams D_{n}, (n\in N) such that the commutativity of D_{n+1} does not imply the commutativity of D_{n}. (In the proof the SMCC of semi-modules over semi-rings are used.) As a consequence the study of dependency of diagrams in SMCCs is much more important than in case of CCC. Various methods of verification of dependency are discussed in the end of the talk.

PETAK, 12.12.2008. U 16:30 SATI
Predrag Tanović (Matematički institut SANU, Beograd)
Fraise-Jonsonova konstrukcija (Fraisse - Jonsson's construction)

Osvrt na poznatu konstrukciju iz teorije modela. Ovo je drugo predavanje iz serije o izabranim temama iz teorije modela. (A review of well known construction in Model theory.)

PETAK, 19.12.2008. u 15:00 SATI

Petar Marković (Departman za Matematiku i Informatiku Prirodno-matematičkog fakulteta Univerziteta u Novom Sadu)
Constraint Satisfaction Problems of bounded width

Abstract: We present an outline of the recent proof by Barto and Kozik that a fixed-template Constraint Satisfaction Problem has bounded width iff the template is invariant under a set of algebraic operations which generates a congruence meet-semidistributive variety. This completely closes off one of the two known algorithmic principles for solving the constraint satisfaction problem in polynomial time by proving it works in the maximal possible environment (the other one was similarly closed off by a team of authors consisting of Berman, Idziak, McKenzie, Valeriote, Willard and the speaker in 2006). The rest of dichotomy conjecture for the complexity of a fixed-template constraint satisfaction problem must be proved using a combinati on of the two algorithmic principles.

PETAK, 26.12.2008. U 16:30 SATI
Aleksandar Perović (Saobraćajni fakultet Univerziteta u Beogradu)
Još o igrama (More on games)

Drugo iz serije predavanja Finite model theory. Preostala dva predavanja su: 3) 0 - 1 zakoni (0 - 1 laws), 4) Zadovoljivost (Satisfiability). Prvo predavanje iz ove serije pod naslovom Erenfojht-Fraiseove igre (Ehrenfeucht-Fraisse games) odrzano je na Seminaru 21. novembra.

Ukoliko zelite mesecne programe ovog Seminara u elektronskom obliku, obratite se: vdjordje@mi.sanu.ac.yu. Programi svih seminara Matematickog instituta SANU nalaze se na sajtu: www.mi.sanu.ac.yu



Rukovodioci Seminara: Kosta Dosen i Djordje Vukomanovic

---