Computational Aspects of Plan-Dependent Model Equivalence: The Case of Knowing-How Bisimulations

Areces, C., Fervari, R., and Mondejar, A.. Computational Aspects of Plan-Dependent Model Equivalence: The Case of Knowing-How Bisimulations. In Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2026), pp. 1323–1331, Association for Computing Machinery, 2026.

Download

[pdf] 

Abstract

We investigate computational aspects of model equivalence for labeled transition systems (LTSs) relative to sets of plans. We focus on the case when model equivalence is defined by a notion of bisimulation in the context of an uncertainty-based knowing-how logic. We start by reformulating such a notion of bisimulation based on purely structural conditions of the LTSs involved, and show adequacy results. Then, we elaborate a computational profile of the new bisimulations. First, we show that the problem of checking whether two LTSs are bisimilar is coNP-complete. Then, we investigate model contractions in order to obtain minimal LTSs, and show that they can be computed in polynomial time.

BibTeX

@inproceedings{areces2026computational,
  author     = {Areces, C. and Fervari, R. and Mondejar, A.},
  title      = {Computational Aspects of Plan-Dependent Model Equivalence: The Case of Knowing-How Bisimulations},
  booktitle = {Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2026)},
  pages     = {1323--1331},
  year      = {2026},
  publisher = {Association for Computing Machinery},
  abstract = {We investigate computational aspects of model
                  equivalence for labeled transition systems (LTSs)
                  relative to sets of plans. We focus on the case when
                  model equivalence is defined by a notion of
                  bisimulation in the context of an uncertainty-based
                  knowing-how logic.  We start by reformulating such a
                  notion of bisimulation based on purely structural
                  conditions of the LTSs involved, and show adequacy
                  results. Then, we elaborate a computational profile
                  of the new bisimulations. First, we show that the
                  problem of checking whether two LTSs are bisimilar
                  is coNP-complete. Then, we investigate model
                  contractions in order to obtain minimal LTSs, and
                  show that they can be computed in polynomial time.},
}