Temporal Properties of Conditional Independence in Dynamic Bayesian Networks

Rajab AghamovRajab Aghamov, Christel BaierChristel Baier, Joël OuaknineJoël Ouaknine, Jakob PiribauerJakob Piribauer, Mihir VahanwalaMihir Vahanwala, Isa VialardIsa Vialard

ISBN: 10: 1-57735-906-2
ISSN: 13: 978-1-57735-906-7
DOI Link

Rajab Aghamov, Christel Baier, Joël Ouaknine, Jakob Piribauer, Mihir Vahanwala, Isa Vialard
Temporal Properties of Conditional Independence in Dynamic Bayesian Networks
In Sven Koenig, Chad Jenkins, Matthew E. Taylor, eds., Proceedings of the 40th Annual AAAI Conference on Artificial Intelligence (AAAI-26), volume 40, 36601–36609, 2026. AAAI Press

Details
Bibtex

KurzfassungAbstract
Dynamic Bayesian networks (DBNs) are compact graphical representations used to model probabilistic systems where interdependent random variables and their distributions evolve over time. In this paper, we study the verification of the evolution of conditional-independence (CI) propositions against temporal logic specifications. To this end, we consider two specification formalisms over CI propositions: linear temporal logic (LTL), and non-deterministic Büchi automata (NBAs). This problem has two variants. Stochastic CI properties take the given concrete probability distributions into account, while structural CI properties are viewed purely in terms of the graphical structure of the DBN. We show that deciding whether a stochastic CI proposition eventually holds is at least as hard as the Skolem problem for linear recurrence sequences, which is a long-standing open problem in number theory. On the other hand, we show that verifying the evolution of structural CI propositions against LTL and NBA specifications is in PSPACE, and is hard for both NP and coNP. We also identify natural restrictions on the graphical structure of the DBN that make the verification of structural CI properties tractable.
Projekt:Project: CPEC, CeTI, SECAI
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

@inproceedings{ABOPVV2026,
  author    = {Rajab Aghamov and Christel Baier and Jo{\"{e}}l Ouaknine and
               Jakob Piribauer and Mihir Vahanwala and Isa Vialard},
  title     = {Temporal Properties of Conditional Independence in Dynamic
               Bayesian Networks},
  editor    = {Sven Koenig and Chad Jenkins and Matthew E. Taylor},
  booktitle = {Proceedings of the 40th Annual {AAAI} Conference on Artificial
               Intelligence (AAAI-26)},
  volume    = {40},
  publisher = {AAAI Press},
  year      = {2026},
  pages     = {36601{\textendash}36609},
  doi       = {10.1609/aaai.v40i43.40983}
}