Th. doct.--Informatique et réseaux--Paris--ENST, 1991. / Bibliogr. p. 171-179.

No description available.

In their recent paper ``Edge-transitive products," Hammack, Imrich, and Klavzar showed that the direct product of connected, non-bipartite graphs is edge-transitive if and only if both factors are edge-transitive, and at least one is arc-transitive. However, little is known when the product is bipartite. This thesis extends this result (in part) for the case of bipartite graphs using a new technique called "stacking." For R-thin, connected, bipartite graphs A and B, we show that A x B is arc-transitive if and only if A and B are both arc-transitive. Further, we show A x B is edge-transitive only if at least one of A, B is also edge-transitive, and give evidence that strongly suggests that in fact both factors must be edge-transitive.

Many problems in bioinformatics are inference problems, that is, the problem objective is to infer something based upon a limited amount of information. In this work we explore two different inference problems in bioinformatics. The first problem is inferring the structure of signal transduction networks from interactions between pairs of cellular components. We present two contributions towards the solution to this problem: an mixed integer program that produces and exact solution, and an implementation of an approximation algorithm in Java that was originally described by DasGupta et al. An exact solution is obtained for a problem instance consisting of real data. The second problem this thesis examines is the problem of inferring complete haplotypes from informative SNPs. In this work we describe two variations of the linear algebraic method for haplotype prediction and tag SNP selection: Two different variants of the algorithm are described and implemented, and the results summarized.

This thesis explores two infinite families of self-complementary arc-transitive graphs: the familiar Paley graphs and the newly discovered Peisert graphs. After studying both families, we examine a result of Peisert which proves the Paley and Peisert graphs are the only self-complementary arc transitive graphs other than one exceptional graph. Then we consider other families of graphs which share many properties with the Paley and Peisert graphs. In particular, we construct an infinite family of self-complementary strongly regular graphs from affine planes. We also investigate the pseudo-Paley graphs of Weng, Qiu, Wang, and Xiang. Finally, we prove a lower bound on the number of maximal cliques of certain pseudo-Paley graphs, thereby distinguishing them from Paley graphs of the same order.

This thesis explores two infinite families of self-complementary arc-transitive graphs: the familiar Paley graphs and the newly discovered Peisert graphs. After studying both families, we examine a result of Peisert which proves the Paley and Peisert graphs are the only self-complementary arc transitive graphs other than one exceptional graph. Then we consider other families of graphs which share many properties with the Paley and Peisert graphs. In particular, we construct an infinite family of self-complementary strongly regular graphs from affine planes. We also investigate the pseudo-Paley graphs of Weng, Qiu, Wang, and Xiang. Finally, we prove a lower bound on the number of maximal cliques of certain pseudo-Paley graphs, thereby distinguishing them from Paley graphs of the same order.

A group G is called a barely transitive group if it acts transitively and faithfully on an infinite set and every orbit of every proper subgroup is finite. A subgroup H of a group G is called a permutable subgroup, if H commutes with every subgroup of G. We showed that if an infinitely generated barely transitive group G has a permutable point stabilizer, then G is locally finite. We proved that if a barely transitive group G has an abelian point stabilizer H, then G is isomorphic to one of the followings: (i) G is a metabelian locally finite p-group, (ii) G is a finitely generated quasi-finite group (in particular H is finite), (iii) G is a finitely generated group with a maximal normal subgroup N where N is a locally finite metabelian group. In particular, G=N is a quasi-finite simple group. In all of the three cases, G is periodic.

Building trust is a common requirement in distributed environments especially since many transactions now occur on a person-to-person basis. Examples range from e-commerce on the Internet to peer-to-peer and grid resource sharing. Many solutions to the problem of requiring trust among unknown entities rely on the use of a reputation metric to assess the risk of a potential transaction. However, such reputation systems require (often implicitly) that trust is transitive which can be a problematic assumption. This dissertation proposes a novel mechanism which we call trust*. The trust* model uses guarantees to extend local trust between unknown end-points. Trust* can be used as a substitution for end-to-end trust. Principals provide guarantees within existing (local) trust relationships to build a chain of localised agreements between the unknown end-points. The guarantees are backed by local micropayments to provide deterrents and incentives. Trust* relationships can be composed transitively, and the guarantees reduce the risk for the trusting party when doing so. This is because a guarantee is only ever provided locally by a directly trusted principal. Thus, trust management can be reduced to a locally solved problem. This work aims to develop a new technique for assessing and reducing the risk involved in trusting others in a distributed environment. The thesis of this dissertation is that an electronic analogue of real-world guarantees, is a useful and interesting way to provide these assurances. We develop an extension of the notion of trust, which we call trust*, which is built upon local guarantees, and which provides a novel conceptual framework for analysing and reasoning about a wide variety of trust-related problems in distributed systems. We present the concept of trust* and apply it to a number of application scenarios where it would be beneficial. We simulate the trust* model in these environments for analysis. Also, we describe the key features and other issues related to the trust* model which became evident during its investigation and which are of wider interest.

We often want to explain and predict behavior, both our own and that of others. For various reasons we want to know not only why (in the sense of etiology) someone is doing what he is, but we also have interests in understanding the agent's reasons for which he is acting as he is. Though not uncontroversial, it is common to cite intentional states when offering such explanations. Most philosophers take certain intentional states to be the causes of our actions and to play a role in accounting for the reasons for which one acts. Additionally, most theorists who adopt such a line take the relevant intentional states to be propositional attitudes, most commonly beliefs and desires (or other pro attitudes which relate one to a proposition). In many of our explanations, we do indeed cite beliefs and desires, but we also cite many other psychological states that aren't obviously beliefs or desires. In fact, some of the relevant psychological states don't even appear to be propositional attitudes. In this paper I pursue two lines of questioning, one about the explanations of action and one about intentionality. First, what role is played by these apparently non-propositional attitudes? Such attitudes turn up in Davidson's locus classicus and can be found in the most recent work on action as well, but explications are sparse. Second, are these attitudes in fact non-propositional? Despite appearances to the contrary, one might argue that such states are to be, in some way or other, assimilated to the more familiar propositional attitudes. I resist this line in the second chapter. / text

Many recent discoveries in animal cognition have shown that species once thought to be relatively simple are in fact capable of complex problem-solving in accordance with their ecological needs. These findings have resulted from experiments designed with the evolutionary history of the focal species in mind. Transitive inference (TI), the abiliy to infer the ordering of non-adjacent objects within a series, is a cognitive skill once thought to be exclusive to humans. Now considered a litmus-test for logical-relational reasoning, TI is thought to have evolved in social species in order to help track dominance relationships. Although recent work has shown that animals can display TI, it has yet to be demonstrated in the natural context in which it evolved. Songbirds may use TI to gain relative dominance information about others during countersinging interactions, through their use of network communication. Here I demonstrate that black-capped chickadees (Poecile atricapillus) use TI to judge the relative rank of unknown territorial intruders during the breeding season using dominance information provided through song contests. Using a multispeaker playback, I provided focal males with the relative ranks of three simulated “males” through two countersinging interactions (A > B, B > C). I predicted that when presented with the non-adjacent pair (A and C) with no relative rank information provided, focal males would choose to defend against the intruder they perceived as the greater threat. Consistent with my predictions, the majority of focal males approached “male” A. Additionally, male responses were influenced by age, with older males (in their second or later breeding season) approaching the dominant intruder more consistently than younger males (in their first breeding season). This is the first instance of TI being demonstrated in a natural population of untrained animals, and has important implications for the understanding of songbird communication networks. Transitive inference may be used in several natural situations by chickadees throughout the breeding season and a number of possible avenues for future TI research are discussed. Additionally, methods are suggested for the examination of TI during the non-breeding season. / Thesis (Master, Biology) -- Queen's University, 2010-09-24 10:45:17.316