Bisimilar States in Uncertain Structures
Rot J, Wißmann T (2023)
Publication Type: Conference contribution
Publication year: 2023
Journal
Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Book Volume: 270
Conference Proceedings Title: Leibniz International Proceedings in Informatics, LIPIcs
Event location: Bloomington, IN, USA
ISBN: 9783959772877
DOI: 10.4230/LIPIcs.CALCO.2023.12
Abstract
We provide a categorical notion called uncertain bisimilarity, which allows to reason about bisimilarity in combination with a lack of knowledge about the involved systems. Such uncertainty arises naturally in automata learning algorithms, where one investigates whether two observed behaviours come from the same internal state of a black-box system that can not be transparently inspected. We model this uncertainty as a set functor equipped with a partial order which describes possible future developments of the learning game. On such a functor, we provide a lifting-based definition of uncertain bisimilarity and verify basic properties. Beside its applications to Mealy machines, a natural model for automata learning, our framework also instantiates to an existing compatibility relation on suspension automata, which are used in model-based testing. We show that uncertain bisimilarity is a necessary but not sufficient condition for two states being implementable by the same state in the black-box system. We remedy the lack of sufficiency by a characterization of uncertain bisimilarity in terms of coalgebraic simulations.
Authors with CRIS profile
Involved external institutions
Netherlands (NL)How to cite
APA:
Rot, J., & Wißmann, T. (2023). Bisimilar States in Uncertain Structures. In Paolo Baldan, Valeria de Paiva (Eds.), Leibniz International Proceedings in Informatics, LIPIcs. Bloomington, IN, USA: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.
MLA:
Rot, Jurriaan, and Thorsten Wißmann. "Bisimilar States in Uncertain Structures." Proceedings of the 10th Conference on Algebra and Coalgebra in Computer Science, CALCO 2023, Bloomington, IN, USA Ed. Paolo Baldan, Valeria de Paiva, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023.
BibTeX: Download