In the context of DFA, it is known that using appropriate data structures, such as trees, and efficiently processing counterexamples lead to significant gains in terms of computation time [1]}, [2]}. To the best of our knowledge, these approaches have not yet been explored for active learning of PDFA.
The algorithms proposed in [3]}, [4]} rely on \(\mathbf {MQ}\)  that compute the probability of a string and on an observation table to store the results.
In [5]}, \(\mathbf {MQ}\)  return state distributions, that is, the probability that the target probabilistic automaton enters a state after reading an input string. This requires knowing the number of states of the target in advance. These works focused on theoretical results without implementations of them being publicly available.
In [6]}, learning PDFA is a building block of an assume-guarantee framework for verification of probabilistic systems. \(\mathbf {MQ}\)  asks for the probability of accepting a string and results are stored in an observation table. However, the overall goal is not to learn a PDFA equivalent to a hidden target but only an appropriate assumption for doing a compositional proof of correctness. To achieve this, the algorithm uses an \(\mathbf {EQ}\)  that relies on language inclusion of PDFA and probabilistic model-checking.
All these works rely on exact equality of \(\mathbf {MQ}\)  outcomes. To deal with noise in distributions, \(\mathrm {WL}^\ast \)  [7]} proposes a non-equivalence similarity relation between probability distributions and develops an algorithm to learn similar hypotheses according to it. Note that \(\mathrm {WL}^\ast \)  uses clustering to group responses to \(\mathbf {MQ}\)  stored in the table.
