Learning Nondeterministic Mealy Machines


Ali Khalili, Armando Tacchella ;
The 12th International Conference on Grammatical Inference, PMLR 34:109-123, 2014.


In applications where abstract models of reactive systems are to be inferred, one important challenge is that the behavior of such systems can be inherently nondeterministic. To cope with this challenge, we developed an algorithm to infer nondeterministic computation models in the form of Mealy machines. We introduce our approach and provide extensive experimental results to assess its potential in the identification of black-box reactive systems. The experiments involve both artificially-generated abstract Mealy machines, and the identification of a TFTP server model starting from a publicly-available implementation.

Related Material