In this dissertation we study groups of automorphisms of rooted trees arising from the transformations of the boundaries of these trees. The boundary of every regular rooted tree can be endowed with various algebraic structures. The transformations of these algebraic structures under certain conditions induce endomorphisms or automorphisms of the tree itself that can be described using the language of Mealy automata. This connection can be used to study boundarytransformations using the propertiesof the induced endomorphisms, or vice versa. We concentrate on two ways to interpret the boundary of the rooted d-regular tree. In the first approach discussed in detail in Chapter 3 we treat it as the ring Zd of d-adic integers. This is achieved by naturally identifying the nth level of the rooted d-ary tree with the ring Z/(dnZ). Under this interpretation we study transformations of Zd induced by polynomials in Z[x]. We show that they always induce endomorphisms of the tree, completely describe these endomorphisms using the language of automata and show that all of their sections are again induced by polynomials in Z[x] of the same degree. In the case of permutational polynomials acting on Zd by bijections the induced endomorphisms are automorphisms of the tree. For d = 2 such polynomials were completely characterized by Rivest in [Riv01]. As our main application we utilize the result of Rivest to derive the conditions on the coefficients of a permutational polynomial f(x) ∈ Z[x] that are necessary and sufficient for f to induce a level transitive automorphism of the binary tree, which is equivalent to the ergodicity of the action of f(x) on Z2 with respect to the normalized Haar measure. Such polynomials have applications in cryptography and are used in certain generators of random numbers. In the second approach, to be discussed in Chapter 4, we treat the boundary of the rooted binary tree as the ring (Z/2Z)[[t]] of formal power series over Z/2Z. This view allowed us to completely describe the structure of a certain group generated by a 4-state 2-letter bireversible automaton. Namely, we show that it is isomorphic to the lamplighter group (Z/2Z)2 ≀ Z of rank two. We show that the action of the generators of this group on the boundary of the tree can be induced by affine transformations of (Z/2Z)[[t]]. To our best knowledge, this is the first realization of the rank 2 lamplighter group by a bireversible automaton.

L'anàlisi de la supervivència s'utilitza en diversos àmbits per tal d'analitzar dades que mesuren el temps transcorregut entre dos successos. També s'anomena anàlisi de la història dels esdeveniments, anàlisi de temps de vida, anàlisi de fiabilitat o anàlisi del temps fins a l'esdeveniment. Una de les dificultats que té aquesta àrea de l'estadística és la presència de dades censurades. El temps de vida d'un individu és censurat quan només és possible mesurar-lo de manera parcial o inexacta. Hi ha diverses circumstàncies que donen lloc a diversos tipus de censura. La censura en un interval fa referència a una situació on el succés d'interès no es pot observar directament i només tenim coneixement que ha tingut lloc en un interval de temps aleatori. Aquest tipus de censura ha generat molta recerca en els darrers anys i usualment té lloc en estudis on els individus són inspeccionats o observats de manera intermitent. En aquesta situació només tenim coneixement que el temps de vida de l'individu es troba entre dos temps d'inspecció consecutius.Aquesta tesi doctoral es divideix en dues parts que tracten dues qüestions importants que fan referència a dades amb censura en un interval. La primera part la formen els capítols 2 i 3 els quals tracten sobre condicions formals que asseguren que la versemblança simplificada pot ser utilitzada en l'estimació de la distribució del temps de vida. La segona part la formen els capítols 4 i 5 que es dediquen a l'estudi de procediments estadístics pel problema de k mostres. El treball que reproduïm conté diversos materials que ja s'han publicat o ja s'han presentat per ser considerats com objecte de publicació.En el capítol 1 introduïm la notació bàsica que s'utilitza en la tesi doctoral. També fem una descripció de l'enfocament no paramètric en l'estimació de la funció de distribució del temps de vida. Peto (1973) i Turnbull (1976) van ser els primers autors que van proposar un mètode d'estimació basat en la versió simplificada de la funció de versemblança. Altres autors han estudiat la unicitat de la solució obtinguda en aquest mètode (Gentleman i Geyer, 1994) o han millorat el mètode amb noves propostes (Wellner i Zhan, 1997).El capítol 2 reprodueix l'article d'Oller et al. (2004). Demostrem l'equivalència entre les diferents caracteritzacions de censura no informativa que podem trobar a la bibliografia i definim una condició de suma constant anàloga a l'obtinguda en el context de censura per la dreta. També demostrem que si la condició de no informació o la condició de suma constant són certes, la versemblança simplificada es pot utilitzar per obtenir l'estimador de màxima versemblança no paramètric (NPMLE) de la funció de distribució del temps de vida. Finalment, caracteritzem la propietat de suma constant d'acord amb diversos tipus de censura. En el capítol 3 estudiem quina relació té la propietat de suma constant en la identificació de la distribució del temps de vida. Demostrem que la distribució del temps de vida no és identificable fora de la classe dels models de suma constant. També demostrem que la probabilitat del temps de vida en cadascun dels intervals observables és identificable dins la classe dels models de suma constant. Tots aquests conceptes elsil·lustrem amb diversos exemples.El capítol 4 s'ha publicat parcialment en l'article de revisió metodològica de Gómez et al. (2004). Proporciona una visió general d'aquelles tècniques que s'han aplicat en el problema no paramètric de comparació de dues o més mostres amb dades censurades en un interval. També hem desenvolupat algunes rutines amb S-Plus que implementen la versió permutacional del tests de Wilcoxon, Logrank i de la t de Student per a dades censurades en un interval (Fay and Shih, 1998). Aquesta part de la tesi doctoral es complementa en el capítol 5 amb diverses propostes d'extensió del test de Jonckeere. Amb l'objectiu de provar una tendència en el problema de k mostres, Abel (1986) va realitzar una de les poques generalitzacions del test de Jonckheere per a dades censurades en un interval. Nosaltres proposem altres generalitzacions d'acord amb els resultats presentats en el capítol 4. Utilitzem enfocaments permutacionals i de Monte Carlo. Proporcionem programes informàtics per a cada proposta i realitzem un estudi de simulació per tal de comparar la potència de cada proposta sota diferents models paramètrics i supòsits de tendència. Com a motivació de la metodologia, en els dos capítols s'analitza un conjunt de dades d'un estudi sobre els beneficis de la zidovudina en pacients en els primers estadis de la infecció del virus VIH (Volberding et al., 1995).Finalment, el capítol 6 resumeix els resultats i destaca aquells aspectes que s'han de completar en el futur. / Survival analysis is used in various fields for analyzing data involving the duration between two events. It is also known as event history analysis, lifetime data analysis, reliability analysis or time to event analysis. One of the difficulties which arise in this area is the presence of censored data. The lifetime of an individual is censored when it cannot be exactly measured but partial information is available. Different circumstances can produce different types of censoring. Interval censoring refers to the situation when the event of interest cannot be directly observed and it is only known to have occurred during a random interval of time. This kind of censoring has produced a lot of work in the last years and typically occurs for individuals in a study being inspected or observed intermittently, so that an individual's lifetime is known only to lie between two successive observation times.This PhD thesis is divided into two parts which handle two important issues of interval censored data. The first part is composed by Chapter 2 and Chapter 3 and it is about formal conditions which allow estimation of the lifetime distribution to be based on a well known simplified likelihood. The second part is composed by Chapter 4 and Chapter 5 and it is devoted to the study of test procedures for the k-sample problem. The present work reproduces several material which has already been published or has been already submitted.In Chapter 1 we give the basic notation used in this PhD thesis. We also describe the nonparametric approach to estimate the distribution function of the lifetime variable. Peto (1973) and Turnbull (1976) were the first authors to propose an estimation method which is based on a simplified version of the likelihood function. Other authors have studied the uniqueness of the solution given by this method (Gentleman and Geyer, 1994) or have improved it with new proposals (Wellner and Zhan, 1997).Chapter 2 reproduces the paper of Oller et al. (2004). We prove the equivalence between different characterizations of noninformative censoring appeared in the literature and we define an analogous constant-sum condition to the one derived in the context of right censoring. We prove as well that when the noninformative condition or the constant-sum condition holds, the simplified likelihood can be used to obtain the nonparametric maximum likelihood estimator (NPMLE) of the failure time distribution function. Finally, we characterize the constant-sum property according to different types of censoring. In Chapter 3 we study the relevance of the constant-sum property in the identifiability of the lifetime distribution. We show that the lifetime distribution is not identifiable outside the class of constant-sum models. We also show that the lifetime probabilities assigned to the observable intervals are identifiable inside the class of constant-sum models. We illustrate all these notions with several examples.Chapter 4 has partially been published in the survey paper of Gómez et al. (2004). It gives a general view of those procedures which have been applied in the nonparametric problem of the comparison of two or more interval-censored samples. We also develop some S-Plus routines which implement the permutational version of the Wilcoxon test, the Logrank test and the t-test for interval censored data (Fay and Shih, 1998). This part of the PhD thesis is completed in Chapter 5 by different proposals of extension of the Jonckeere's test. In order to test for an increasing trend in the k-sample problem, Abel (1986) gives one of the few generalizations of the Jonckheree's test for interval-censored data. We also suggest different Jonckheere-type tests according to the tests presented in Chapter 4. We use permutational and Monte Carlo approaches. We give computer programs for each proposal and perform a simulation study in order compare the power of each proposal under different parametric assumptions and different alternatives. We motivate both chapters with the analysis of a set of data from a study of the benefits of zidovudine in patients in the early stages of the HIV infection (Volberding et al., 1995).Finally, Chapter 6 summarizes results and address those aspects which remain to be completed.

A sign pattern matrix is a matrix whose entries are from the set {+,-,0}. For a real matrix B, sgn(B) is the sign pattern matrix obtained by replacing each positive(respectively, negative, zero) entry of B by + (respectively, -, 0). For a sign pattern matrix A, the sign pattern class of A, denoted Q(A), is defined as {B: sgn(B) = A}. An n by n sign pattern matrix A requires all distinct eigenvalues if every real matrix whose sign pattern is represented by A has n distinct eigenvalues. In this thesis, a number of sufficient and/or necessary conditions for a sign pattern to reuiqre all distinct eigenvalues are reviewed. In addition, for n=2 and 3, the n by n sign patterns that require all distinct eigenvalues are surveyed. We determine most of the 4 by 4 irreducible sign patterns that require four distinct eigenvalues.

A group G is called an FC-group if the conjugacy class of every element is finite. G is called a minimal non-FC-group if G is not an FC-group, but every proper subgroup of G is an FC-group. The first part of this thesis is on minimal non-FC-groups and their finitary permutational representations. Belyaev proved in 1998 that, every perfect locally finite minimal non-FC-group has non-trivial finitary permutational representation. In Chapter 3, we write the proof of Belyaev in detail. Recall that a group G is called quasi-simple if G is perfect and G/Z(G) is simple. The second part of this thesis is on finite quasi-simple groups and their coprime automorphisms. In Chapter 4, the result of Parker and Quick is written in detail: Namely / if Q is a quasi-simple group and A is a non-trivial group of coprime automorphisms of Q satisfying |Q: C_{Q}(A)| &lt / n then |Q| &lt / n3, that is |Q| is bounded by a function of n.

Este trabalho é dedicado ao problema de programação em Flowshop Permutacional com tempos de preparação (setup) assimétricos e separados dos tempos de processamento e dependentes da seqüência de execução das tarefas e tem o objetivo de minimização da duração total da programação (Makespan). Através da investigação das propriedades estruturais do problema, são desenvolvidos os parâmetros XR e QR de uma programação, que indicam ociosidade das máquinas (para valores positivos) e bloqueio das tarefas (para valores negativos). Os novos parâmetros são utilizados para propor uma melhoria no cálculo eficiente de Makespan proposto por Taillard (1990). Esta melhoria é então utilizada no desenvolvimento de uma nova heurística construtiva baseada no método NEHT-RB de Ríos-Mercado e Bard (1998b) denominada CNIT, que é comparada durante a experimentação computacional com os métodos SETUP e TOTAL, de Simons (1992) com pequenas melhorias; com a proposta da utilização da propriedade UBX de Moccellin e Nagano (2007); e com o método NEHT-RB. Os métodos são então submetidos a uma busca local descendente como proposta em Ruiz e Stützle (2008) e seus desempenhos como soluções iniciais para este procedimento de busca local são avaliados. Em seguida, um método melhorativo derivado do novo método construtivo e baseado na meta-heurística IG de Ruiz e Stützle (2008) é proposto e denominado CNIT-IG. O método é comparado com a heurística IG original submetida às diferentes soluções iniciais estudadas durante a avaliação da nova heurística construtiva. As comparações são realizadas utilizando-se o banco de dados de Taillard (1990) para o flowshop permutacional adaptado para o problema de flowshop com tempos de setup assimétricos e dependentes da seqüência. Os resultados da experimentação computacional são analisados em termos da porcentagem média de sucesso, do desvio relativo médio e em relação ao tempo médio computacional e mostram a superioridade dos resultados da nova heurística construtiva CNIT e seu alto custo computacional, de complexidade mn³. Os resultados mostram ainda a superioridade da meta-heurística CNIT-IG sobre o método IG. / This work addresses the Permutation Flowshop scheduling problem with separated sequence-dependent setup times with the objective of minimizing Makespan. Through the investigation of the problem structural properties, two scheduling parameters XR e QR are developed, they indicate the machine idleness (for positive values) and task blocking (for negative values). These new parameters are used to propose an improvement in the efficient makespan calculation as stated by Taillard (1990). This improvement is then used for development of a new constructive heuristic based on Ríos-Mercado and Bard (1998b) method NEHT-RB nominated CNIT, and it is compared during computational experimentation with the methods SETUP and TOTAL of Simons (1992), with slight improvements; with the proposal of property UBX from Moccellin and Nagano (2007) and with NEHT-RB method. The methods are then submitted to descent local search as proposed in Ruiz and Stützle (2008) and its performance as initial solutions for this local search procedure is evaluated. Next, an improvement method derivate from the new constructive method and based on metaheuristic IG from Ruiz and Stützle (2008) is proposed and nominated CNIT-IG. This method is compared with original IG submitted to different initial solutions studied during constructive heuristic evaluation. Comparisons are done using Taillards instances (1990) for standard flowshop and adapted to the flowshop with sequencedependent setup times problem. The results of computation experimentation are analyzed in terms of average percentage of success, average relative percentage deviation and average computational time and show superiority of new constructive heuristic CNIT-IG and its high computational cost, with complexity mn³. The results also show superiority of metaheuristic CNIT-IG over IG method.

Este trabalho é dedicado ao problema de programação em Flowshop Permutacional com tempos de preparação (setup) assimétricos e separados dos tempos de processamento e dependentes da seqüência de execução das tarefas e tem o objetivo de minimização da duração total da programação (Makespan). Através da investigação das propriedades estruturais do problema, são desenvolvidos os parâmetros XR e QR de uma programação, que indicam ociosidade das máquinas (para valores positivos) e bloqueio das tarefas (para valores negativos). Os novos parâmetros são utilizados para propor uma melhoria no cálculo eficiente de Makespan proposto por Taillard (1990). Esta melhoria é então utilizada no desenvolvimento de uma nova heurística construtiva baseada no método NEHT-RB de Ríos-Mercado e Bard (1998b) denominada CNIT, que é comparada durante a experimentação computacional com os métodos SETUP e TOTAL, de Simons (1992) com pequenas melhorias; com a proposta da utilização da propriedade UBX de Moccellin e Nagano (2007); e com o método NEHT-RB. Os métodos são então submetidos a uma busca local descendente como proposta em Ruiz e Stützle (2008) e seus desempenhos como soluções iniciais para este procedimento de busca local são avaliados. Em seguida, um método melhorativo derivado do novo método construtivo e baseado na meta-heurística IG de Ruiz e Stützle (2008) é proposto e denominado CNIT-IG. O método é comparado com a heurística IG original submetida às diferentes soluções iniciais estudadas durante a avaliação da nova heurística construtiva. As comparações são realizadas utilizando-se o banco de dados de Taillard (1990) para o flowshop permutacional adaptado para o problema de flowshop com tempos de setup assimétricos e dependentes da seqüência. Os resultados da experimentação computacional são analisados em termos da porcentagem média de sucesso, do desvio relativo médio e em relação ao tempo médio computacional e mostram a superioridade dos resultados da nova heurística construtiva CNIT e seu alto custo computacional, de complexidade mn³. Os resultados mostram ainda a superioridade da meta-heurística CNIT-IG sobre o método IG. / This work addresses the Permutation Flowshop scheduling problem with separated sequence-dependent setup times with the objective of minimizing Makespan. Through the investigation of the problem structural properties, two scheduling parameters XR e QR are developed, they indicate the machine idleness (for positive values) and task blocking (for negative values). These new parameters are used to propose an improvement in the efficient makespan calculation as stated by Taillard (1990). This improvement is then used for development of a new constructive heuristic based on Ríos-Mercado and Bard (1998b) method NEHT-RB nominated CNIT, and it is compared during computational experimentation with the methods SETUP and TOTAL of Simons (1992), with slight improvements; with the proposal of property UBX from Moccellin and Nagano (2007) and with NEHT-RB method. The methods are then submitted to descent local search as proposed in Ruiz and Stützle (2008) and its performance as initial solutions for this local search procedure is evaluated. Next, an improvement method derivate from the new constructive method and based on metaheuristic IG from Ruiz and Stützle (2008) is proposed and nominated CNIT-IG. This method is compared with original IG submitted to different initial solutions studied during constructive heuristic evaluation. Comparisons are done using Taillards instances (1990) for standard flowshop and adapted to the flowshop with sequencedependent setup times problem. The results of computation experimentation are analyzed in terms of average percentage of success, average relative percentage deviation and average computational time and show superiority of new constructive heuristic CNIT-IG and its high computational cost, with complexity mn³. The results also show superiority of metaheuristic CNIT-IG over IG method.

Nitrogen-fixing bacteria in soybean nodules convert atmospheric nitrogen to plant-available forms in exchange for carbon from the plant, but other non-nitrogen-fixing bacteria also reside in nodules, and their role in the nodule is not well understood. This study was conducted to determine the effect of three non-nitrogen-fixing Pseudomonas spp. strains isolated from nodules on soybean, and we hypothesized these strains benefit soybean. A greenhouse study in which two cultivars of soybean (Asgrow AG46X6 and Pioneer P48A60X) were treated with three fluorescent Pseudomonas spp. strains (referred to in this study as Bullseye, Pancake, and Starfish) and an uninoculated control. Soybeans were harvested at two time points: the R2/R3 growth stage and the R6 growth stage. Following each harvest, measures of growth, yield, and nitrogen fixation were taken, and data were analyzed using two non-parametric, multivariate analyses: multiple response permutation procedure (MRPP) and permutational multivariate analysis of variance (PERMANOVA). Both analyses showed soybeans of both cultivars treated with Pancake differed from controls following the first harvest but not the second. When analyzed individually, most metrics for growth, yield, and nitrogen fixation following the first harvest were not significantly different between Pancake and control treatments, but Pancake treatment means were still generally higher than controls. If metrics are considered collectively in conjunction with the results of the multivariate analyses, the results show Pancake generally increased soybean growth and nitrogen fixation. These findings support the hypothesis that non-nitrogen-fixing bacteria from nodules benefit plants, and such bacteria have the potential to serve as biofertilizers. / Master of Science in Life Sciences / Soybeans are one of the most commonly grown crops in the world, and nitrogen-fixing bacteria colonize the roots of soybeans and initiate the formation of spherical nodules attached to the roots. Inside the nodules, these bacteria convert atmospheric nitrogen to plant-available forms in exchange for sugar from the plant, and such bacteria reduce the need to add nitrogen fertilizer to agricultural fields. Other non-nitrogen-fixing bacteria also reside in nodules, but their role in the nodule is not well understood. If these bacteria benefit soybeans, they have the potential to serve as biofertilizers (microbial inoculants that promote plant growth). This study was conducted to determine whether non-nitrogen-fixing bacteria isolated from nodules benefit soybean. A greenhouse study in which two cultivars of soybean (Asgrow AG46X6 and Pioneer P48A60X) were grown in soil and were either left uninoculated or were inoculated with one of three strains of bacteria from the genus, Pseudomonas (referred to in this study as Bullseye, Pancake, and Starfish). Following harvest, measures of growth, yield, and nitrogen fixation were taken, and data showed the bacteria generally benefited the soybean plants. Although, these results showed the bacteria benefitted the plants, field trials and further testing in the greenhouse should be conducted before using these bacteria as commercial biofertilizers. Additionally, the effects of other non-nitrogen-fixing nodule bacteria on soybeans should also be tested to identify other beneficial strains, and the cost of production should be compared to the potential gains of using such bacteria before they are developed into biofertilizers.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal