Probabilistic Strategy Logic
Authors: Benjamin Aminof, Marta Kwiatkowska, Bastien Maubert, Aniello Murano, Sasha Rubin
IJCAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We introduce Probabilistic Strategy Logic, an extension of Strategy Logic for stochastic systems. ... We study the model-checking problem for agents with perfect- and imperfect-recall. The former is undecidable, while the latter is decidable in space exponential in the system and triple-exponential in the formula. We identify a natural fragment of the logic, in which every temporal operator is immediately preceded by a probabilistic operator, and show that it is decidable in space exponential in the system and the formula, and double-exponential in the nesting depth of the probabilistic terms. ... To prove these results we reduce to the first-order theory of real arithmetic, known to be decidable in EXPSPACE [Ben Or et al., 1986]. |
| Researcher Affiliation | Academia | Benjamin Aminof1,2 , Marta Kwiatkowska3 , Bastien Maubert4 , Aniello Murano4 and Sasha Rubin4 1JKU Linz, Austria 2TU Wien, Austria 3University of Oxford, UK 4Universit a degli Studi di Napoli Federico II, Italy |
| Pseudocode | No | The paper describes a translation process but does not include structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not mention providing access to source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not refer to any datasets. |
| Dataset Splits | No | The paper is theoretical and does not discuss dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not provide any hardware specifications for running experiments. |
| Software Dependencies | No | The paper does not provide specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup or hyperparameters. |