Thomas Neele: Compositional Learning of Synchronous Automata


Event Details


The classical L* algorithm for learning DFAs runs in polynomial time with the size of the DFA being learnt. However, the DFA that represents a system consisting of multiple parallel components can grow exponentially in the number of components; known as the state space explosion problem. In this talk I will demonstrate how, given the ability to ask membership and equivalence queries for a (large) composite system, we can learn its constituting components independently. This way, we can avoid the state explosion and improve the performance of learning parallel systems in practice.