0
$\begingroup$

This question is about the TTT algorithm for blackbox automata inference as defined in [1] and [2]. I am finding it difficult to understand all the innovations made by the algorithm. I understand how

  1. Discrimination tree is important in pairwise distinguishing of states (as opposed to observation table approach)
  2. I understand the necessity of finding the shortest suffix from the counter example, and how binary search (and exponential back-off) works for identifying such a suffix quickly compared to linear search
  3. I also understand the prefix transformation, which can reduce the long prefix from the counter example (what remains after finding the shortest suffix) to the smallest prefix supported by the learned automata.

However,

(a) I am finding it difficult to understand the intuition behind discriminator finalization. Is it the idea that a counter example may contain more than one novel state, and we can find such novel states by searching from the right most end of the counter example, at each point where the learned DFA and the blackbox differ? (b) Is there any other innovation I am missing? (c) Are there any better performing algorithms out there for DFA learning? I am familiar with L# and variants [3], and ADT [4], but the performance seems roughly on par with TTT? (Fig 4)[3] and [5].

Finally, it seems the biggest jump in terms of performance so far has been the discrimination tree. Is this correct? Looking at Table 5.2 of [2], the performance of OP, KV and TTT are roughly in the same ballpark.

[1]: The TTT algorithm: a redundancy-free approach to active automata learning

[2]: Foundations of Active Automata Learning: An Algorithmic Perspective

[3]: A New Approach for Active Automata Learning Based on Apartness

[4]: Active Automata Learning with Adaptive Distinguishing Sequences

[5]: Benchmarking Combinations of Learning and Testing Algorithms for Automata Learning

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

If you get a counterexample back from the teacher the counterexample is very long. If the suffix analysis is used as described in the paper, the suffix can be very long, this suffix is added in the discrimination tree, whenever you sift in the discrimination tree on a path with the newly added discriminator, for a word that is at least as long as the suffix a membership query is asked. This can take very long - note that equivalence queries are often in reality just a membershipquery on a very long word. In order to make the suffix which is the discriminator shorter, discriminator finalization is used and the node with the long discriminator gets replaced with a node with a short discriminator and therefore membership queries are cheaper

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for the response. Is there any chance you could expand this with an example? Also, when you say /This can take long/ do you mean that a single query can take a long time because is is a long query? $\endgroup$
    – Rahul Gopinath
    Commented Jan 20 at 8:25
  • $\begingroup$ I am working on an example... $\endgroup$
    – Coping Forever
    Commented Jan 28 at 23:28
  • $\begingroup$ Isberners motivation for the TTT algorithm was to combine "desirable" properties of different algorithms in order to obtain an optimal algorithm, for this he extended the OP algorithm and extended it with discriminator finalization which is a process motivated by discrimination tree based algorithms in a white box setting instead of a black box setting. He noticed that the whitebox does not need to be exploited and it can also be applied to the blackbox setting. $\endgroup$
    – Coping Forever
    Commented Jan 28 at 23:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.