6 Search Results for "van Ditmarsch, Hans"

Document
DOI: 10.4230/LIPIcs.CSL.2026.35
Boolean Basis and Succinctness of Modal Logic via Hella-Vilander Games

Authors: Sebastian Pfau

Published in: LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026)

Abstract
The Hella-Vilander game for modal logic is a model comparison game that captures the formula size necessary to separate sets of pointed Kripke structures. We introduce the ℳ-ON game as a modification of this game. Our game captures the necessary number of modal operators, i.e., ◇ and □ instead of formula size. We use our game to show that the bi-implication ↔, sometimes also called equivalence, enables us to write modal logic formula with significantly fewer modal operators. With this we show, that with bi-implications we can also write significantly shorter modal logic formulas. This result holds even if only special classes of Kripke structures are considered. To be more precise we show that there is an exponential succinctness gap between modal logic and its extension with bi-implication on the class of structures with a transitive and reflexive accessibility relation, as well as on the class of structures with a symmetrical and reflexive accessibility relation. Lastly we show that for the class of structures with a transitive and symmetrical accessibility relation this succinctness gap disappears.
Cite as

Sebastian Pfau. Boolean Basis and Succinctness of Modal Logic via Hella-Vilander Games. In 34th EACSL Annual Conference on Computer Science Logic (CSL 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 363, pp. 35:1-35:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{pfau:LIPIcs.CSL.2026.35,
  author =	{Pfau, Sebastian},
  title =	{{Boolean Basis and Succinctness of Modal Logic via Hella-Vilander Games}},
  booktitle =	{34th EACSL Annual Conference on Computer Science Logic (CSL 2026)},
  pages =	{35:1--35:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-411-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{363},
  editor =	{Guerrini, Stefano and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.35},
  URN =		{urn:nbn:de:0030-drops-254600},
  doi =		{10.4230/LIPIcs.CSL.2026.35},
  annote =	{Keywords: succinctness, modal logic, model comparison games}
}
Document
DOI: 10.4230/DagRep.13.7.34
Epistemic and Topological Reasoning in Distributed Systems (Dagstuhl Seminar 23272)

Authors: Armando Castañeda, Hans van Ditmarsch, Roman Kuznets, Yoram Moses, and Ulrich Schmid

Published in: Dagstuhl Reports, Volume 13, Issue 7 (2024)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23272 "Epistemic and Topological Reasoning in Distributed Systems." The seminar brought together experts in combinatorial topology and epistemic logic interested in distributed systems, with the aim of exploring the directions that the recent interaction between those approaches can take, identifying challenges and opportunities.
Cite as

Armando Castañeda, Hans van Ditmarsch, Roman Kuznets, Yoram Moses, and Ulrich Schmid. Epistemic and Topological Reasoning in Distributed Systems (Dagstuhl Seminar 23272). In Dagstuhl Reports, Volume 13, Issue 7, pp. 34-65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{castaneda_et_al:DagRep.13.7.34,
  author =	{Casta\~{n}eda, Armando and van Ditmarsch, Hans and Kuznets, Roman and Moses, Yoram and Schmid, Ulrich},
  title =	{{Epistemic and Topological Reasoning in Distributed Systems (Dagstuhl Seminar 23272)}},
  pages =	{34--65},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{13},
  number =	{7},
  editor =	{Casta\~{n}eda, Armando and van Ditmarsch, Hans and Kuznets, Roman and Moses, Yoram and Schmid, Ulrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.7.34},
  URN =		{urn:nbn:de:0030-drops-197742},
  doi =		{10.4230/DagRep.13.7.34},
  annote =	{Keywords: combinatorial topology, distributed systems, epistemic logic, multi-agent systems, interpreted systems, dynamic epistemic logic, simplicial semantics, knowledge-based approach, distributed computing}
}
Document
DOI: 10.4230/DagRep.7.6.1
Epistemic Planning (Dagstuhl Seminar 17231)

Authors: Chitta Baral, Thomas Bolander, Hans van Ditmarsch, and Sheila McIlrath

Published in: Dagstuhl Reports, Volume 7, Issue 6 (2018)

Abstract
The seminar Epistemic Planning brought together the research communities of Dynamic Epistemic Logic, Knowledge Representation and Reasoning, and Automated Planning to address fundamental problems on the topic of epistemic planning. In the context of this seminar, dynamic epistemic logic investigates the formal semantics of communication and communicative actions, knowledge representation and reasoning focuses on theories of action and change, and automated planning investigates computational techniques and tools to generate plans. The original goals of the seminar were to develop benchmarks for epistemic planning, to explore the relationship between knowledge and belief in multi-agent epistemic planning, to develop models of agency and capability in epistemic planning and to explore action types and their representations (these originally separate goals were merged during the seminar), and finally to identify practical tools and resources. An additional goal explored during the workshop was the correspondence between planning problems and games.
Cite as

Chitta Baral, Thomas Bolander, Hans van Ditmarsch, and Sheila McIlrath. Epistemic Planning (Dagstuhl Seminar 17231). In Dagstuhl Reports, Volume 7, Issue 6, pp. 1-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{baral_et_al:DagRep.7.6.1,
  author =	{Baral, Chitta and Bolander, Thomas and van Ditmarsch, Hans and McIlrath, Sheila},
  title =	{{Epistemic Planning (Dagstuhl Seminar 17231)}},
  pages =	{1--47},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{6},
  editor =	{Baral, Chitta and Bolander, Thomas and van Ditmarsch, Hans and McIlrath, Sheila},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.6.1},
  URN =		{urn:nbn:de:0030-drops-82857},
  doi =		{10.4230/DagRep.7.6.1},
  annote =	{Keywords: Automated Planning, Knowledge Representation and Reasoning, Reasoning About Actions, Dynamic Epistemic Logic, Multi-Agent Systems}
}
Document
DOI: 10.4230/DagSemProc.09351.3
Awareness and forgetting of facts and agents

Authors: Hans Van Ditmarsch and Tim French

Published in: Dagstuhl Seminar Proceedings, Volume 9351, Information processing, rational belief change and social interaction (2009)

Abstract
We propose various logical semantics for change of awareness. The setting is that of multiple agents that may become aware of facts or other agents, or forget about them. We model these dynamics by quantifying over propositional variables and agent variables, in a multi-agent epistemic language with awareness operators, employing a notion of bisimulation with a clause for `same awareness'. The quantification is over all different ways in which an agent can become aware (or forget). Logics for change of awareness combine well with logics for informational change, as when a public announcement simultaneously makes you aware of an issue (`a plane just crashed on Schiphol Airport').
Cite as

Hans Van Ditmarsch and Tim French. Awareness and forgetting of facts and agents. In Information processing, rational belief change and social interaction. Dagstuhl Seminar Proceedings, Volume 9351, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{vanditmarsch_et_al:DagSemProc.09351.3,
  author =	{Van Ditmarsch, Hans and French, Tim},
  title =	{{Awareness and forgetting of facts and agents}},
  booktitle =	{Information processing, rational belief change and social interaction},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9351},
  editor =	{Giacomo Bonanno and James Delgrande and Hans Rott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09351.3},
  URN =		{urn:nbn:de:0030-drops-22286},
  doi =		{10.4230/DagSemProc.09351.3},
  annote =	{Keywords: Awareness, knowledge, multi-agent systems, dynamics}
}
Document
DOI: 10.4230/DagSemProc.07351.15
Optimal Regression for Reasoning about Knowledge and Actions

Authors: Hans van Ditmarsch, Andreas Herzig, and Tiago de Lima

Published in: Dagstuhl Seminar Proceedings, Volume 7351, Formal Models of Belief Change in Rational Agents (2007)

Abstract
We show how in the propositional case both Reiter's and Scherl & Levesque's solutions to the frame problem can be modelled in dynamic epistemic logic (DEL), and provide an optimal regression algorithm for the latter. Our method is as follows: we extend Reiter's framework by integrating observation actions and modal operators of knowledge, and encode the resulting formalism in DEL with announcement and assignment operators. By extending Lutz' recent satisfiability-preserving reduction to our logic, we establish optimal decision procedures for both Reiter's and Scherl & Levesque's approaches: satisfiability is NP-complete for one agent, PSPACE-complete for multiple agents and EXPTIME-complete when common knowledge is involved.
Cite as

Hans van Ditmarsch, Andreas Herzig, and Tiago de Lima. Optimal Regression for Reasoning about Knowledge and Actions. In Formal Models of Belief Change in Rational Agents. Dagstuhl Seminar Proceedings, Volume 7351, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{vanditmarsch_et_al:DagSemProc.07351.15,
  author =	{van Ditmarsch, Hans and Herzig, Andreas and de Lima, Tiago},
  title =	{{Optimal Regression for Reasoning about Knowledge and Actions}},
  booktitle =	{Formal Models of Belief Change in Rational Agents},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7351},
  editor =	{Giacomo Bonanno and James Delgrande and J\'{e}r\^{o}me Lang and Hans Rott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07351.15},
  URN =		{urn:nbn:de:0030-drops-12077},
  doi =		{10.4230/DagSemProc.07351.15},
  annote =	{Keywords: Reasoning about action and change, reasoning about knowledge, situation calculus, frame problem, dynamic epistemic logic}
}
Document
DOI: 10.4230/DagSemProc.05321.6
Belief change and dynamic logic

Authors: Hans van Ditmarsch

Published in: Dagstuhl Seminar Proceedings, Volume 5321, Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics (2005)

Abstract
In this paper we compare standard ways to perform belief change with attempts to model such change with dynamic modal operators. We address both belief expansion, belief contraction, belief revision, and update. Public announcement logic is an implementation of a belief expansion operator in a dynamic epistemic setting. The postulates of success and minimal change cannot be satisfied in their original AGM formulation. Dynamic doxastic logic provides various implementations of a belief revision operator in a dynamic epistemic setting. We provide an example of the application of such a dynamic doxastic semantics, which can also be seen as a realization of a proposal by Spohn. The purpose of this paper is to provide an overview of different approaches to dynamic logics for belief change, including some of our own contributions to the area, in a way that is accessible to an interdisciplinary audience. It does not contain new technical results not published elsewhere. However, the comparison of different approaches provides, we hope, new insights not seen before. A final version of this paper may include new technical results.
Cite as

Hans van Ditmarsch. Belief change and dynamic logic. In Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics. Dagstuhl Seminar Proceedings, Volume 5321, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{vanditmarsch:DagSemProc.05321.6,
  author =	{van Ditmarsch, Hans},
  title =	{{Belief change and dynamic logic}},
  booktitle =	{Belief Change in Rational Agents: Perspectives from Artificial Intelligence, Philosophy, and Economics},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5321},
  editor =	{James Delgrande and Jerome Lang and Hans Rott and Jean-Marc Tallon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05321.6},
  URN =		{urn:nbn:de:0030-drops-3376},
  doi =		{10.4230/DagSemProc.05321.6},
  annote =	{Keywords: Belief revision, dynamic epistemic logic}
}
  • Refine by Type
  • 6 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2024
  • 1 2017
  • 1 2009
  • 1 2007
  • Show More...

  • Refine by Author
  • 4 van Ditmarsch, Hans
  • 1 Baral, Chitta
  • 1 Bolander, Thomas
  • 1 Castañeda, Armando
  • 1 French, Tim
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 2 DagRep
  • 3 DagSemProc

  • Refine by Classification
  • 1 Computing methodologies → Distributed algorithms
  • 1 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Topology
  • 1 Software and its engineering → Distributed systems organizing principles
  • 1 Software and its engineering → Formal methods
  • Show More...

  • Refine by Keyword
  • 3 dynamic epistemic logic
  • 2 multi-agent systems
  • 1 Automated Planning
  • 1 Awareness
  • 1 Belief revision
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact