2026-07-22T13:39:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18809 2024-03-06T11:01:55Z ddc:004 open_access

Bisimilar States in Uncertain Structures Rot, Jurriaan Wißmann, Thorsten Coalgebra Relation Lifting Bisimilarity Mealy Machines ioco 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jurriaan Rot and Thorsten Wißmann 2023 Is Part Of LIPIcs, Volume 270, 10th Conference on Algebra and Coalgebra in Computer Science (CALCO 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CALCO.2023.12 urn:nbn:de:0030-drops-188094 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2023.12 eng https://creativecommons.org/licenses/by/4.0/legalcode