Models that can represent the behavior of systems, such as a Finite State Machine (FSM), are crucial for software development and maintenance as they serve as a base for several automated activities like testing, verification, validation, and refinement of systems. Contrasting their importance and value, models are usually complex and costly to obtain. One option to mitigate this problem is model inference which provides the possibility to automatically, or at least with little human interaction, learn a model that represents the behavior of a system. This process can be mainly classified into passive inference (builds models from examples of the behavior of a system) and active inference (builds models from interacting with the system). In this dissertation, we propose a method for learning separating sequences from traces (examples of a previously observed behavior of the system) and applying it to improve the process of model inference. A separating sequence is an input sequence capable of distinguishing a pair of distinct states of a machine by yielding different output sequences for each state. When a set of separating sequences distinguishes all pairs of distinct states in the FSM, it is called a characterization set, or W-set. Our proposed method receives a set of traces, processes them to extract all their k-length subsequences, and uses them to build a data structure called W-tree that summarizes the relevant observations of the systems behavior indicated in the traces. The methods output is a set of the n-best separating sequences that a model inference algorithm applies to improve its W-set and its inference process. We implemented our proposed method, integrated it with an active inference algorithm called hW -inference, and performed a case study in which we used 40 different traces. We observed that the proposed method could improve the learning process by 24%, on average, and up to 48% in the best-case setting.

Modelos capazes de representar o comportamento de sistemas, como uma Máquina de Estado Finitos (MEF), são essenciais para o desenvolvimento e a manutenção de software, pois servem de base para várias atividades automatizadas, tais como teste, verificação, validação e refinamento de sistemas. Em contrapartida a sua importância, modelos geralmente são complexos e custosos para se obter. Uma opção para amenizar esse problema é a inferência de modelos, que permite inferir automaticamente, ou com pouca interação humana, um modelo que represente o comportamento do sistema. Esse processo pode ser classificado principalmente em inferência passiva (infere modelos a partir de exemplos do comportamento de um sistema) e inferência ativa (infere modelos a partir da interação com o sistema). Nesta dissertação, é proposto um método para inferir sequências de separação a partir de traces (exemplos observados previamente do comportamento do sistema) e aplicá-las para aprimorar o processo de inferência de modelos. Uma sequência de separação é uma sequência de símbolos de entrada capaz de distinguir um par de estados distintos de uma MEF ao produzir sequências de saída diferentes para cada estado. Quando um conjunto de sequências de separação distingue todos os pares de estados distintos em uma MEF, ele é chamado de conjunto de caracterização, ou W-set. O método proposto recebe um conjunto de traces e os processa para extrair todas as suas subsequências de comprimento k, criando uma estrutura de dados chamada W-tree que resume as observações relevantes do comportamento do sistema indicado nos traces. O resultado do método é um conjunto das n melhores sequências de separação que um algoritmo de inferência de modelo pode aplicar para aprimorar seu W-set e seu processo de inferência. O método proposto foi implementado, integrado a um algoritmo de inferencia ativa chamado hW -inference, e um estudo de caso foi conduzido, no qual foram empregados 40 traces diferentes. Como principal resultado do experimento, foi observado que o método proposto pode melhorar o processo de aprendizagem em 24%, em média, e em até 48% em seu melhor caso.