In this section we present the results of the experiments carried out to compare \(\mathrm {QuaNT}\)  with a clustering-based algorithm that uses an observation table and a tolerance-based non-equivalence similarity relation, similar to \(\mathrm {WL}^\ast \) , that we call \(\mathrm {L_{p}^\ast }\)  (see Appendix ). We compared the learning algorithms on randomly generated PDFA.
The generation technique works in two steps. First, it constructs random DFA over \(\Sigma \) . Second, DFA are transformed into PDFA by assigning a probability distribution over \(\Sigma _\$\)  to every state.
The first step uses the method described in [1]} based on results from [2]}. Let \(n\)  be the desired number of reachable states of a DFA, called its nominal size. The method consists in randomly generating DFA of a total of \(n\cdot m\cdot \rho _{m}^{-1}\)  possibly unreachable states, for \(m = |\Sigma |\) , where \(\rho _{m} = m - W_{0}\cdot m\cdot e^{-m}\)  and \(W_{0}\)  is the Lambert-W function, and then computing its accessible part by a depth-first traversal.
It is important to remark that this method does not guarantee the actual size of the accessible part to be exactly \(n\) , but to be normally distributed around \(n\) . To obtain exactly \(n\)  accessible states, the method could be repeated using a rejection algorithm. However, in practice, this proved to be very inefficient, being almost impossible to generate DFA of accessible size bigger than 100 in reasonable time. All experiments threw perfect scores for all computed metrics (word error rate, normalized discounted cumulative gain, log probability error [3]}) for all algorithms on the same test set of strings. Therefore, the analyses of the experimental results are mainly focused on execution time and structure size. For ease of comparison, figures show trend lines.
