BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Model Checking for Modal Intuitionistic Dependence Logic - Yang\, 
 F (University of Helsinki)
DTSTART:20120326T150000Z
DTEND:20120326T153000Z
UID:TALK37092@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:In this paper we consider the complexity of model checking for
  modal intuitionistic dependence logic (MIDL). MIDL is a natural variant o
 f first-order dependence logic (D)\, which was introduced by Vnnen (2007)\
 , as a new approach to independence-friendly logic (Hintikka\, Sandu\, 198
 9). Sentences of D have exactly the same expressive power as sentences of 
 existential second-order logic (Vnnen 2007\, c.f. Enderton\, 1970 and Walk
 oe\, 1970). The compositional semantics of D is team semantics\, originall
 y developed by Hodges (1997) for independence-friendly logic. Abramsky and
  Vnnen (2009) studied Hodges construction in a more general context and in
 troduced BID-logic\, which extends dependence and includes intuitionistic 
 implication\, Boolean disjunction\, as well as linear implication. It was 
 shown that the intuitionistic fragment of BID-logic\, called intuitionisti
 c dependence logic\, has exactly the same expressive power as the full sec
 ond-order logic\, on the level of sentences (Yang\, 2010). \n\nThe modal v
 ersion of D\, modal dependence logic (MDL) was defined by Vnnen (2008). A 
 natural variant of MDL is modal intuitionistic dependence logic\, where th
 e intuitionistic implication and Boolean disjunction are added into the se
 tting. In this paper we show that the model checking problem for MIDL in g
 eneral is PSPACE-complete. Furthermore\, we consider fragments of MIDL bui
 lt by restricting the operators allowed in the logic. It turns out that ap
 art from known NP-complete as well as tractable fragments there also are s
 ome coNP-complete fragments\, e.g. propositional intuitionistic dependence
  logic.\n\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR