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.

We provide a simple and improved security analysis of PMAC, a Parallelizable MAC (Message Authentication Code) defined over arbitrary messages. A similar kind of result was shown by Bellare, Pietrzak and Rogaway at Crypto 2005, where they have provided an improved bound for CBC (Cipher Block Chaining) MAC, which was introduced by Bellare, Killan and Rogaway at Crypto 1994. Our analysis idea is much more simpler to understand and is borrowed from the work by Nandi for proving Indistinguishability at Indocrypt 2005 and work by Bernstein. It shows that the advantage for any distinguishing attack for n-bit PMAC based on a random function is bounded by O(??q / 2^n), where ?? is the total number of blocks in all q queries made by the attacker. In the original paper by Black and Rogaway at Eurocrypt 2002 where PMAC was introduced, the bound is O(??^2 / 2^n). We also compute the collision probability of CBC MAC for suitably chosen messages. We show that the probability is ??( lq^2 / N) where l is the number of message blocks, N is the size of the domain and q is the total number of queries. For random oracles the probability is O(q^2 / N). This improved collision probability will help us to have an efficient distinguishing attack and MAC-forgery attack. We also show that the collision probability for PMAC is ??(q^2 / N) (strictly greater than the birthday bound). We have used a purely combinatorial approach to obtain this bound. Similar analysis can be made for other CBC MAC extensions like XCBC, TMAC and OMAC.

<p> When pigeons are required to discriminate between two displays which may only be differentiated by a distinctive feature on one of the two displays, subjects trained with the distinctive feature on the positive display learn the successive discrimination while subjects trained with the distinctive feature on the negative display do not. The simultaneous discrimination theory of this "feature-positive effect" makes a number of explicit predictions about the behaviour of the feature positive and feature negative subjects. The present experiments were designed to test these predictions. Experiment I tested the prediction of localization on the distinctive feature by feature positive subjects while Experiment II tested the prediction of avoidance of the distinctive feature by feature negative subjects. Experiment III attempted to reduce the feature-positive effect by presenting compact displays.</p> <p> The results of these three experiments supported the simultaneous discrimination theory of the feature positive effect.</p> / Thesis / Doctor of Philosophy (PhD)

No description available.

We provide a simple and improved security analysis of PMAC, a Parallelizable MAC (Message Authentication Code) defined over arbitrary messages. A similar kind of result was shown by Bellare, Pietrzak and Rogaway at Crypto 2005, where they have provided an improved bound for CBC (Cipher Block Chaining) MAC, which was introduced by Bellare, Killan and Rogaway at Crypto 1994. Our analysis idea is much more simpler to understand and is borrowed from the work by Nandi for proving Indistinguishability at Indocrypt 2005 and work by Bernstein. It shows that the advantage for any distinguishing attack for n-bit PMAC based on a random function is bounded by O(σq / 2^n), where σ is the total number of blocks in all q queries made by the attacker. In the original paper by Black and Rogaway at Eurocrypt 2002 where PMAC was introduced, the bound is O(σ^2 / 2^n). We also compute the collision probability of CBC MAC for suitably chosen messages. We show that the probability is Ω( lq^2 / N) where l is the number of message blocks, N is the size of the domain and q is the total number of queries. For random oracles the probability is O(q^2 / N). This improved collision probability will help us to have an efficient distinguishing attack and MAC-forgery attack. We also show that the collision probability for PMAC is Ω(q^2 / N) (strictly greater than the birthday bound). We have used a purely combinatorial approach to obtain this bound. Similar analysis can be made for other CBC MAC extensions like XCBC, TMAC and OMAC.

A distinguishing colouring of a graph G is a labelling of the vertices of G with colours such that no non-trivial automorphism of G preserves all colours. The distinguishing number of G is the minimum number of colours in a distinguishing colouring. This thesis presents a survey of the history of distinguishing colouring problems and proves new bounds and computational results about distinguishability. An algorithm to generate all labellings of a graph up to isomorphism is presented and compared to a previously published algorithm. The new algorithm is shown to have performance competitive with the existing algorithm, as well as being able to process automorphism groups far larger than the previous limit. A specialization of the algorithm is used to generate all minimal distinguishing colourings of a set of graphs with large automorphism groups and compute their distinguishing numbers. / Graduate / 0984 / 0405 / bbird@uvic.ca

Vertex-distinguishing edge-colorings (vdec colorings) are a restriction of proper edge-colorings. These special colorings require that the sets of edge colors incident to every vertex be distinct. This is a relatively new field of study. We present a survey of known results concerning vdec colorings. We also define a new matrix which may be used to study vdec colorings, and examine its properties. We find several bounds on the eigenvalues of this matrix, as well as results concerning its determinant, and other properties. We finish by examining related topics and open problems.

Vertex-distinguishing edge-colorings (vdec colorings) are a restriction of proper edge-colorings. These special colorings require that the sets of edge colors incident to every vertex be distinct. This is a relatively new field of study. We present a survey of known results concerning vdec colorings. We also define a new matrix which may be used to study vdec colorings, and examine its properties. We find several bounds on the eigenvalues of this matrix, as well as results concerning its determinant, and other properties. We finish by examining related topics and open problems.

Nessa dissertação, pretendemos analisar a valorização dos precedentes judiciais pelo Direito Processual Civil brasileiro. Para tanto, no primeiro capítulo faremos algumas considerações gerais sobre os sistemas de common e civil law, principalmente no tocante ao tema desta pesquisa: os precedentes judiciais. Diante da comparação entre os dois sistemas, poderemos demonstrar que há uma inegável aproximação entre eles, principalmente no que concerne aos precedentes judiciais. Com relação ao Direito brasileiro, muito embora a valorização dos precedentes seja alternativa eficaz para propiciar segurança jurídica e igualdade ao jurisdicionado, e imprimir celeridade à marcha processual, as técnicas de operação com precedentes já existentes, recentemente inseridas e aquelas que se pretende inserir, devem ser pensadas à luz dos referidos princípios constitucionais e de acordo com a nossa realidade. Nesse contexto, estudaremos, no segundo capítulo, os princípios que orientam o tema da presente pesquisa, para que possamos, no terceiro capítulo, analisar individualmente cada técnica processual relacionada ao nosso tema, de forma a verificar a contribuição que cada uma trouxe ao ordenamento jurídico, bem como ao ideal de concretização dos princípios relacionados no capítulo anterior. Por fim, no quarto capítulo abordaremos o Projeto do novo Código de Processo Civil, que, conforme será demonstrado, dá continuidade ao movimento de valorização dos precedentes judiciais pelo Direito Processual Civil brasileiro, na medida em que estabelece normas para vinculação dos Juízes e Tribunais ao entendimento dos Tribunais superiores, bem como cria novo mecanismos de operação com precedentes judiciais. / In this work, we intend to analyze the enhancement of judicial precedents by the Brazilian Civil Procedure Law. In this end, in the first chapter, we will make some general remarks on the common law and civil law systems, especially regarding the topic of this research: judicial precedents. Following the comparison of these two systems, we will be able to demonstrate that there is an undeniable closeness between them, especially with regard to judicial precedents. With respect to Brazilian Law, although the contemporary tendency towards increasing the significance of precedent is an effective alternative that provides legal certainty and equality to all citizens, and to expedite Court proceedings, the procedural techniques regarding precedents should be analyzed in light of the constitutional principles listed above and in accordance with our reality. In this context, in the second chapter, we study the principles that guide the focus of this research, so that, in the third chapter, we can individually analyze each procedural technique related to our topic, in order to verify the contribution that they make to the legal system, as well as to the ideal of embodiment of the principles listed in the previous chapter. Finally, in the fourth chapter, we will discuss the project of the new Code of Civil Procedure, which, as will be shown, continues the movement towards increasing the value of judicial precedents by Brazilian Civil Procedure Law, extending the standards for binding lower court judges to the understandings of the higher courts and creating new mechanisms for operating with judicial precedents.

Nessa dissertação, pretendemos analisar a valorização dos precedentes judiciais pelo Direito Processual Civil brasileiro. Para tanto, no primeiro capítulo faremos algumas considerações gerais sobre os sistemas de common e civil law, principalmente no tocante ao tema desta pesquisa: os precedentes judiciais. Diante da comparação entre os dois sistemas, poderemos demonstrar que há uma inegável aproximação entre eles, principalmente no que concerne aos precedentes judiciais. Com relação ao Direito brasileiro, muito embora a valorização dos precedentes seja alternativa eficaz para propiciar segurança jurídica e igualdade ao jurisdicionado, e imprimir celeridade à marcha processual, as técnicas de operação com precedentes já existentes, recentemente inseridas e aquelas que se pretende inserir, devem ser pensadas à luz dos referidos princípios constitucionais e de acordo com a nossa realidade. Nesse contexto, estudaremos, no segundo capítulo, os princípios que orientam o tema da presente pesquisa, para que possamos, no terceiro capítulo, analisar individualmente cada técnica processual relacionada ao nosso tema, de forma a verificar a contribuição que cada uma trouxe ao ordenamento jurídico, bem como ao ideal de concretização dos princípios relacionados no capítulo anterior. Por fim, no quarto capítulo abordaremos o Projeto do novo Código de Processo Civil, que, conforme será demonstrado, dá continuidade ao movimento de valorização dos precedentes judiciais pelo Direito Processual Civil brasileiro, na medida em que estabelece normas para vinculação dos Juízes e Tribunais ao entendimento dos Tribunais superiores, bem como cria novo mecanismos de operação com precedentes judiciais. / In this work, we intend to analyze the enhancement of judicial precedents by the Brazilian Civil Procedure Law. In this end, in the first chapter, we will make some general remarks on the common law and civil law systems, especially regarding the topic of this research: judicial precedents. Following the comparison of these two systems, we will be able to demonstrate that there is an undeniable closeness between them, especially with regard to judicial precedents. With respect to Brazilian Law, although the contemporary tendency towards increasing the significance of precedent is an effective alternative that provides legal certainty and equality to all citizens, and to expedite Court proceedings, the procedural techniques regarding precedents should be analyzed in light of the constitutional principles listed above and in accordance with our reality. In this context, in the second chapter, we study the principles that guide the focus of this research, so that, in the third chapter, we can individually analyze each procedural technique related to our topic, in order to verify the contribution that they make to the legal system, as well as to the ideal of embodiment of the principles listed in the previous chapter. Finally, in the fourth chapter, we will discuss the project of the new Code of Civil Procedure, which, as will be shown, continues the movement towards increasing the value of judicial precedents by Brazilian Civil Procedure Law, extending the standards for binding lower court judges to the understandings of the higher courts and creating new mechanisms for operating with judicial precedents.