Suppose Gamma is a group acting on a set X. An r-labeling phi: X to {1, 2, ..., r} of X is distinguishing (with respect to the action of Gamma) if for any sigma in Gamma, sigma not equal id_X, there exists an element x in X such that phi(x) not equal phi(sigma(x)). The distinguishing number, D_{Gamma}(X), of the action of Gamma on X is the minimum r for which there is an r-labeling which is distinguishing. Given a graph G, the distinguishing number of G, D(G),is defined as D(G) = D_{Aut(G)}(V(G)). This thesis determines the distinguishing numbers of all actions of S_5. As a consequence, we determine all the possible values of the distinguishing numbers of graphs G with Aut(G)=S_5, confirming a conjecture of Albertson and Collins.

O teste de software engloba diferentes técnicas, métodos e conceitos capazes de garantir a qualidade dos mais variados tipos de sistemas. Dentre tais técnicas, encontra-se o teste baseado em Máquinas de Estados Finitos (MEFs), que visa a garantir a conformidade entre a implementação e a especificação de um software. Com esse propósito, diversos métodos foram propostos para a geração de seqüências de verificação que garantam cobertura total das possíveis falhas existentes em uma implementação. A maioria dos métodos conhecidos são baseados na utilização de seqüências de distinção. Esse recurso, porem, não existe para toda MEF. Alguns métodos buscam a geração de seqüências de verificação baseados em recursos alternativos as seqüências de distinção, contudo, as seqüências geradas são exponencialmente longas. Este trabalho apresenta um método para geração de seqüências de verificação que visa a reduzir o tamanho das seqüências geradas para o domínio de MEFs que não dispõem de seqüência de distinção. Para isso, o método proposto baseia-se na utilização de conjuntos de distinção. Uma avaliação experimental foi realizada afim de mensurar a redução proporcionada pelo método proposto em relação aos principais métodos existentes na literatura. Com esse intuito, foram geradas MEFs aleatórias sob a perspectiva diferentes fatores. Em relação a variação do número de estados, os resultados indicaram reduções acima de 99; 5% em comparação com os métodos existentes, quando analisadas 75% das MEFs geradas / Software testing involves several techniques, methods, and concepts employed to guarantee a high level of quality in different application domains. Among such techniques, Finite State Machine (FSM) based testing aims to guarantee the conformance between the implementation and the specification of a system under test. In this context, several methods were proposed to generate checking sequences that cover all the possible faults existing in an implementation. Most of these methods are based on a special sequence, named distinguishing sequence, which does not exist for every minimal machine. Some methods were proposed to generate checking sequences based on alternative solutions in order to be applied on FSMs that do not have distinguishing sequences. However, these methods generate checking sequences exponentially long. This work proposes a method to generate checking sequences using identification sets. These sets exist for every minimal FSM and also lead to shorter checking sequences. We conducted an experimental study to compare the proposed method with the main existing methods. In the experiments, we used random FSMs that have different configurations of states, inputs, and outputs. Concerning the variation of number of states, the results show reductions higher than 99:5% in comparison with the existing methods for 75% of the experimented machines

O teste de software engloba diferentes técnicas, métodos e conceitos capazes de garantir a qualidade dos mais variados tipos de sistemas. Dentre tais técnicas, encontra-se o teste baseado em Máquinas de Estados Finitos (MEFs), que visa a garantir a conformidade entre a implementação e a especificação de um software. Com esse propósito, diversos métodos foram propostos para a geração de seqüências de verificação que garantam cobertura total das possíveis falhas existentes em uma implementação. A maioria dos métodos conhecidos são baseados na utilização de seqüências de distinção. Esse recurso, porem, não existe para toda MEF. Alguns métodos buscam a geração de seqüências de verificação baseados em recursos alternativos as seqüências de distinção, contudo, as seqüências geradas são exponencialmente longas. Este trabalho apresenta um método para geração de seqüências de verificação que visa a reduzir o tamanho das seqüências geradas para o domínio de MEFs que não dispõem de seqüência de distinção. Para isso, o método proposto baseia-se na utilização de conjuntos de distinção. Uma avaliação experimental foi realizada afim de mensurar a redução proporcionada pelo método proposto em relação aos principais métodos existentes na literatura. Com esse intuito, foram geradas MEFs aleatórias sob a perspectiva diferentes fatores. Em relação a variação do número de estados, os resultados indicaram reduções acima de 99; 5% em comparação com os métodos existentes, quando analisadas 75% das MEFs geradas / Software testing involves several techniques, methods, and concepts employed to guarantee a high level of quality in different application domains. Among such techniques, Finite State Machine (FSM) based testing aims to guarantee the conformance between the implementation and the specification of a system under test. In this context, several methods were proposed to generate checking sequences that cover all the possible faults existing in an implementation. Most of these methods are based on a special sequence, named distinguishing sequence, which does not exist for every minimal machine. Some methods were proposed to generate checking sequences based on alternative solutions in order to be applied on FSMs that do not have distinguishing sequences. However, these methods generate checking sequences exponentially long. This work proposes a method to generate checking sequences using identification sets. These sets exist for every minimal FSM and also lead to shorter checking sequences. We conducted an experimental study to compare the proposed method with the main existing methods. In the experiments, we used random FSMs that have different configurations of states, inputs, and outputs. Concerning the variation of number of states, the results show reductions higher than 99:5% in comparison with the existing methods for 75% of the experimented machines