BEGIN:VCALENDAR
VERSION:2.0
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:19700329T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:19701025T030000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
SUMMARY:
Dependence and Independence in Logic
STATUS:CONFIRMED
ATTENDEE;CN="Erich Grädel
":
MAILTO:no@spam.com
DESCRIPTION:
There have been a number of proposals for incorporating the
concepts of dependence or independence into mathematical log
ic. Classical variants include Henkin quantifiers and indepe
ndence friendly logics; a more modern approach\, triggered b
y Väänänen's dependence logic\, treats notions of dependence
and independence as atomic properties and not as annotation
s of quantifiers\, and has motivated the construction and an
alysis of a large variety of logics based on different notio
ns of dependence and independence\, many of which have close
connections to dependency concepts from database theory. Th
e key difference to classical logical formalisms is that dep
endence and independence manifest themselves not for a singl
e assignment\, mapping variables to elements of a structure\
, but only for a set of such assignments. Accordingly\, mode
l-theoretic semantics for logics of dependence and independe
nce refer to structures together with a set of assignments (
called a team) and thus differ substantially from the Tarski
-style semantics of first-order logic\, second-order logic a
nd similar formalisms. We shall describe different logics of
dependence and independence and examine their expressive po
wer. We design model-checking games for logics with team sem
antics in a general and systematic way. The second-order fea
tures of team semantics are reflected by the notion of a con
sistent winning strategy which is also a second-order notion
in the sense that it depends not on single plays but on the
space of all plays that are compatible with the strategy. B
eyond the application to logics with team semantics\, we iso
late an abstract\, purely combinatorial definition of such g
ames\, which may be viewed as second-order reachability game
s\, and study their algorithmic properties. A number of exam
ples are provided that show how logics with team semantics e
xpress familiar combinatorial problems in a somewhat unexpec
ted way. Based on our games\, we provide a complexity analys
is of logics with teams semantics. We shall also discuss the
recently discovered connections between logics with team se
mantics and fixed-point logics\, and analyze these connectio
ns in game-theoretic terms.
DTSTART;TZID=Europe/Paris:20140610T110000
DURATION:PT1H
URL;VALUE=URI:http://www.lsv.ens-cachan.fr/Seminaires/?sem=201406101
100
UID:LSVsemLSV.201406101100@lsv.ens-cachan.fr
LOCATION:Auditorium Daniel Chemla (Bât. Institut D'Alembert)
END:VEVENT
END:VCALENDAR