Small Undecidable Problems in Epistemic Planning
Authors: Sébastien Lê Cong, Sophie Pinchinat, François Schwarzentruber
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We exhibit a small undecidable subclass of epistemic planning over 2-agent S5 models with a fixed repertoire of one action, 6 propositions and a fixed goal. We furthermore consider a variant of the epistemic planning problem where the initial knowledge state is an automatic structure, hence possibly infinite. In that case, we show the epistemic planning problem with 1 public action and 2 propositions to be undecidable, while it is known to be decidable with public actions over finite models. Our results are obtained by reducing the reachability problem over small universal cellular automata. |
| Researcher Affiliation | Academia | Sébastien Lê Cong1, Sophie Pinchinat1, François Schwarzentruber1 1 Univ Rennes, CNRS, IRISA sebastien.le-cong@irisa.fr, sophie.pinchinat@univ-rennes1.fr, francois.schwarzentruber@ens-rennes.fr |
| Pseudocode | No | The paper describes the logic and construction of actions formally and with diagrams (e.g., Figure 3), but it does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper refers to an online software 'Hintikka s world' (http://hintikkasworld.irisa.fr) for DEL simulations, but it does not explicitly state that the source code for the methodology described in this paper is openly available or provide a link to such code. |
| Open Datasets | No | This is a theoretical paper focusing on undecidability proofs in epistemic planning, and as such, it does not involve training models on datasets or mention public datasets for this purpose. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical validation with data splits. |
| Hardware Specification | No | This is a theoretical paper focused on logical proofs and does not describe any specific hardware used for experiments. |
| Software Dependencies | No | The paper mentions 'Hintikka s world' as online software for simulations, but it does not provide specific version numbers for it or any other software dependencies relevant to replicating the theoretical work. |
| Experiment Setup | No | This is a theoretical paper focused on logical proofs and does not include details about an experimental setup, hyperparameters, or training configurations. |