Seminar for
Mathematical Logic
PROGRAM
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
PETAK, 12.12.2008. U 16:30 SATI
PETAK, 26.12.2008. U 16:30 SATI
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
Seminara za logiku za decembar 2008.
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.
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.
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.
Rukovodioci Seminara: Kosta Dosen i Djordje Vukomanovic