Polynomial-time complexity for instances of the endomorphism problem in free groups

We say the endomorphism problem is solvable for an element W in a free group F if it can be decided effectively whether, given U in F, there is an endomorphism Φ of F sending W to U. This work analyzes an approach due to C. Edmunds and improved by C. Sims. Here we prove that the approach provides an efficient algorithm for solving the endomorphism problem when W is a two- generator word. We show that when W is a two-generator word this algorithm solves the problem in time polynomial in the length of U. This result gives a polynomial-time algorithm for solving, in free groups, two-variable equations in which all the variables occur on one side of the equality and all the constants on the other side.

The complexity of random ordered structures

"Vegeu el resum a l'inici del document del fitxer adjunt."

The Catalan countries project (1931-1939)

In the evolution of Catalan nationalism, as much politician as cultural, the period of II Spanish Republic (1931-1939) was essential. The obtaining of the Statute of Autonomy (1931-1932) supposed the beginning of a stage of expansion in multiple aspects. One of them were the contacts with the Catalanists nuclei of the rest of the cultural space of Catalan language in which, at that time, it would begin to call Catalan Countries (Balearic Islands, Valencian Country, Andorra, Rosselló, to l'Alguer). On Those Collaborations between cultural organizations, political and particular parties Catalonia always will be the model to follow. The Increasing connections will be visualized on press, as well as on cultural celebrations, policy of parties and Constituent Courts. This evolution will be cut by the Franco victory in the Civil War in 1939.

Transferring QTL technology to the pig breeding industry (PigQTech) - a demonstration project

The aim of the project has been to demonstrate how the farm animal breeding industry can utilise gene mapping technology to accelerate genetic improvement. Previous theoretical studies had suggested that the use of marker assisted selection could potentially increase the annual improvement for quantitative traits like backfat with about 10% and for more difficult traits such as meat quality and reproduction by as much as 40-60% compared with existing technology. The work has comprised two major tasks: 1. Commercially relevant populations have been screened for segregation at QTLs identified in experimental populations. The aim has been to establish optimal strategies for QTL detection in commercial pig populations and the extent to which QTLs explaining major phenotypic differences between divergent lines used in experimental studies also explain quantitative variation within commercial lines. The results are important for specifying future strategies for finding economically valuable QTLs. 2. Marker assisted backcrossing has been used to demonstrate how a QTL allele can be introgressed from one breed to another. The work has focused on the major fatness QTL on pig chromosome 4 previously identified in a wild pig/Large White intercross. The end result was not designed to be a commercially viable product in its own right, but the process has validated a number of points of major importance for the exploitation of QTLs in livestock.

On the complexity of the Whitehead minimization problem

The Whitehead minimization problem consists in finding a minimum size element in the automorphic orbit of a word, a cyclic word or a finitely generated subgroup in a finite rank free group. We give the first fully polynomial algorithm to solve this problem, that is, an algorithm that is polynomial both in the length of the input word and in the rank of the free group. Earlier algorithms had an exponential dependency in the rank of the free group. It follows that the primitivity problem – to decide whether a word is an element of some basis of the free group – and the free factor problem can also be solved in polynomial time.

Construcció modular d'agents basats en components: estudi i desenvolupament

La complexitat de disseny d’agents mòbils creix a mesura que s’incrementen les seves funcionalitats. Aquest projecte proposa enfocar el problema des d’un punt de vista modular. S’ha realitzat un estudi tant dels propis agents com de les parts que ho integren. De la mateixa forma, s’han establert i s'han implementat els mecanismes necessaris per habilitar les comunicacions segures entre agents. Finalment, s’han desenvolupat dos components que ofereixen les funcionalitats de seguiment de l’agent mòbil i la recuperació dels resultats generats. El desenvolupament d’agents basats en components tracta d’aplicar la vella estratègia "divideix i venceràs" a la fase de disseny, reduint, així,la seva gran complexitat.

Inequality and a repeated joint project

Agents voluntarily contribute to an infinitely repeated joint project. We investigate the conditions for cooperation to be a renegotiation-proof and coalition-proof equilibrium before examining the influence of output share inequality on the sustainability of cooperation. When shares are not equally distributed, cooperation requires agents to be more patient than under perfect equality. Beyond a certain degree of share inequality, full efficiency cannot be reached without redistribution. This model also explains the coexistence of one cooperating and one free-riding coalition. In this case, increasing inequality can have a positive or negative impact on the aggregate level of effort.

Behind the Scenes of an Ant Genome Project

Dramatic improvements in DNA sequencing technologies have led to amore than 1,000-fold reduction in sequencing costs over the past five years.Genome-wide research approaches can thus now be applied beyond medicallyrelevant questions to examine the molecular-genetic basis of behavior,development and unique life histories in almost any organism. A first step foran emerging model organism is usually establishing a reference genomesequence. I offer insight gained from the fire ant genome project. First, I detailhow the project came to be and how sequencing, assembly and annotationstrategies were chosen. Subsequently, I describe some of the issues linked toworking with data from recently sequenced genomes. Finally, I discuss anapproach undertaken in a follow-up project based on the fire ant genomesequence.

Functional sphere profiling reveals the complexity of neuroblastoma tumor-initiating cell model.

Neuroblastoma (NB) is a neural crest-derived childhood tumor characterized by a remarkable phenotypic diversity, ranging from spontaneous regression to fatal metastatic disease. Although the cancer stem cell (CSC) model provides a trail to characterize the cells responsible for tumor onset, the NB tumor-initiating cell (TIC) has not been identified. In this study, the relevance of the CSC model in NB was investigated by taking advantage of typical functional stem cell characteristics. A predictive association was established between self-renewal, as assessed by serial sphere formation, and clinical aggressiveness in primary tumors. Moreover, cell subsets gradually selected during serial sphere culture harbored increased in vivo tumorigenicity, only highlighted in an orthotopic microenvironment. A microarray time course analysis of serial spheres passages from metastatic cells allowed us to specifically "profile" the NB stem cell-like phenotype and to identify CD133, ABC transporter, and WNT and NOTCH genes as spheres markers. On the basis of combined sphere markers expression, at least two distinct tumorigenic cell subpopulations were identified, also shown to preexist in primary NB. However, sphere markers-mediated cell sorting of parental tumor failed to recapitulate the TIC phenotype in the orthotopic model, highlighting the complexity of the CSC model. Our data support the NB stem-like cells as a dynamic and heterogeneous cell population strongly dependent on microenvironmental signals and add novel candidate genes as potential therapeutic targets in the control of high-risk NB.

The Importance of Revenue Sharing for the Local Economic Impacts of a Renewable Energy Project: A Social Accounting Matrix Approach

As demand for electricity from renewable energy sources grows, there is increasing interest, and public and financial support, for local communities to become involved in the development of renewable energy projects. In the UK, “Community Benefit” payments are the most common financial link between renewable energy projects and local communities. These are “goodwill” payments from the project developer for the community to spend as it wishes. However, if an ownership stake in the renewable energy project were possible, receipts to the local community would potentially be considerably higher. The local economic impacts of these receipts are difficult to quantify using traditional Input-Output techniques, but can be more appropriately handled within a Social Accounting Matrix (SAM) framework where income flows between agents can be traced in detail. We use a SAM for the Shetland Islands to evaluate the potential local economic and employment impact of a large onshore wind energy project proposed for the Islands. Sensitivity analysis is used to show how the local impact varies with: the level of Community Benefit payments; the portion of intermediate inputs being sourced from within the local economy; and the level of any local community ownership of the project. By a substantial margin, local ownership confers the greatest economic impacts for the local community.

Automatización de la gestión del ciclo de vida de entornos Linux y Solaris

Los requisitos del Negocio que requieren un gran crecimiento generan mayor complejidad en los Centros de Cómputo.Son los administradores quienes necesitan gestionar el creciente volumen de datos, aplicaciones, y usuarios, así como la rápida proliferación de los servidores y los diferentes sistemas operativos. En este proyecto se pretende reducir la complejidad en la gestión de los Centros de Cómputo, combinando la automatización de la gestión del ciclo de vida y todas las medidas de contingencia necesarias para mantener la integridad de los mismos.

Desenvolupament d'un component de tolerància a fallades per a un sistema d'agents mòbils sobre plataformes lleugeres

A mesura que la complexitat de les tasques dels agents mòbils va creixent, és més important que aquestes no perdin el treball realitzat. Hem de saber en tot moment que la execució s’està desenvolupant favorablement. Aquest projecte tracta d’explicar el procés d’elaboració d’un component de tolerància a fallades des de la seva idea inicial fins a la seva implementació. Analitzarem la situació i dissenyarem una solució. Procurarem que el nostre component emmascari la fallada d’un agent, detectant-la i posteriorment recuperant l’execució des d’on s’ha interromput. Tot això procurant seguir la metodologia de disseny d’agents mòbils per a plataformes lleugeres.

Object recognition for autonomous objects: comparison of two approaches

Report for the scientific sojourn at the Swiss Federal Institute of Technology Zurich, Switzerland, between September and December 2007. In order to make robots useful assistants for our everyday life, the ability to learn and recognize objects is of essential importance. However, object recognition in real scenes is one of the most challenging problems in computer vision, as it is necessary to deal with difficulties. Furthermore, in mobile robotics a new challenge is added to the list: computational complexity. In a dynamic world, information about the objects in the scene can become obsolete before it is ready to be used if the detection algorithm is not fast enough. Two recent object recognition techniques have achieved notable results: the constellation approach proposed by Lowe and the bag of words approach proposed by Nistér and Stewénius. The Lowe constellation approach is the one currently being used in the robot localization project of the COGNIRON project. This report is divided in two main sections. The first section is devoted to briefly review the currently used object recognition system, the Lowe approach, and bring to light the drawbacks found for object recognition in the context of indoor mobile robot navigation. Additionally the proposed improvements for the algorithm are described. In the second section the alternative bag of words method is reviewed, as well as several experiments conducted to evaluate its performance with our own object databases. Furthermore, some modifications to the original algorithm to make it suitable for object detection in unsegmented images are proposed.