Responsibility Anticipation and Attribution in LTLf
Authors: Giuseppe De Giacomo, Emiliano Lorini, Timothy Parker, Gianmarco Parretti
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we study different variants of responsibility for LTLf outcomes based on strategic reasoning. We show a connection with notions in reactive synthesis, including the synthesis of winning, dominant, and best-effort strategies. This connection provides a strong computational grounding of responsibility, allowing us to characterize the worst-case computational complexity and devise sound, complete, and optimal algorithms for anticipating and attributing responsibility. We prove membership of checking active responsibility by exhibiting a sound and complete algorithm to solve it. |
| Researcher Affiliation | Academia | Giuseppe De Giacomo1,2 , Emiliano Lorini3 , Timothy Parker3 and Gianmarco Parretti2 1University of Oxford 2University of Rome La Sapienza 3IRIT, CNRS, Toulouse University, France EMAIL, EMAIL, EMAIL EMAIL |
| Pseudocode | Yes | We begin by giving an algorithm to check if a strategy σag is winning for φ under E, denoted CHECKWIN(φ, E, σag): 1. Construct the NFA N φ of φ, the DFA AE of E, and the DFA Aσag of σag; 2. Restrict AE to the environment winning region and obtain DFA A E; and 3. Check language nonemptiness of the product N = N φ A E Aσag. |
| Open Source Code | No | The paper does not contain any explicit statement about open-sourcing code, nor does it provide links to code repositories or mention code in supplementary materials. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments on specific datasets. The examples provided (e.g., “The plant is watered”) are illustrative scenarios and do not refer to actual datasets. |
| Dataset Splits | No | The paper does not involve empirical experiments using datasets, therefore, no dataset splits are discussed. |
| Hardware Specification | No | The paper focuses on theoretical contributions, computational complexity, and algorithm design, without describing any experimental setup or hardware used for running experiments. |
| Software Dependencies | No | The paper describes theoretical algorithms and complexity analysis but does not mention specific software dependencies with version numbers used for implementing or executing experiments. |
| Experiment Setup | No | The paper is theoretical and focuses on formalizing concepts, analyzing complexity, and designing algorithms. It does not describe any empirical experimental setup, hyperparameters, or training configurations. |