1. Cédric Dégremont, Lena Kurzen & Jakub Szymanik (2012). Exploring the Tractability Border in Epistemic Tasks. Synthese (3):1-38.
    We analyse the computational complexity of comparing informational structures. Intuitively, we study the complexity of deciding queries such as the following: Is Alice’s epistemic information strictly coarser than Bob’s? Do Alice and Bob have the same knowledge about each other’s knowledge? Is it possible to manipulate Alice in a way that she will have the same beliefs as Bob? The results show that these problems lie on both sides of the border between tractability (P) and intractability (NP-hard). In particular, we (...)
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  2. Cédric Dégremont, Lena Kurzen & Jakub Szymanik (2011). On theTractability of Comparing Informational Structures. In J. van Eijck & R. Verbrugge (eds.), Proceedings of the Workshop 'Reasoning about other minds: Logical and cognitive perspectives.
  3. Lena Kurzen (2009). Reasoning About Cooperation, Actions and Preferences. Synthese 169 (2):223 - 240.
    In this paper, a logic for reasoning about coalitional power is developed which explicitly represents agents’ preferences and the actions by which the agents can achieve certain results. A complete axiomatization is given and its satisfiability problem is shown to be decidable and EXPTIME -hard.
    No categories
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation