Bounding right-arm rotation distances

Rotation distance quantifies the difference in shape between two rooted binary trees of the same size by counting the minimum number of elementary changes needed to transform one tree to the other. We describe several types of rotation distance, and provide upper bounds on distances between trees with a fixed number of nodes with respect to each type. These bounds are obtained by relating each restricted rotation distance to the word length of elements of Thompson's group F with respect to different generating sets, including both finite and infinite generating sets.

Absolute type shaft encoding using LFSR

Maximal-length binary sequences have been known for a long time. They have many interesting properties, one of them is that when taken in blocks of n consecutive positions they form 2ⁿ-1 different codes in a closed circular sequence. This property can be used for measuring absolute angular positions as the circle can be divided in as many parts as different codes can be retrieved. This paper describes how can a closed binary sequence with arbitrary length be effectively designed with the minimal possible block-length, using linear feedback shift registers (LFSR). Such sequences can be used for measuring a specified exact number of angular positions, using the minimal possible number of sensors that linear methods allow.

Tree automorphisms and quasi-isometries of Thompson's group F

We prove that automorphisms of the infinite binary rooted tree T2 do not yield quasi-isometries of Thompson's group F, except for the map which reverses orientation on the unit interval, a natural outer automorphism of F. This map, together with the identity map, forms a subgroup of Aut(T2) consisting of 2-adic automorphisms, following standard terminology used in the study of branch groups. However, for more general p, we show that the analgous groups of p-adic tree automorphisms do not give rise to quasiisometries of F(p).

Códigos binarios no lineales en MAGMA

La finalitat d'aquest projecte és aconseguir representar codis binaris no lineals de manera eficient en un ordinador. Per fer-ho, hem desenvolupat funcions per representar un codi binari a partir del super dual. Hem millorat la funció de càlcul del kernel d'un codi binari, implementada en projectes d'anys anteriors. També hem desenvolupat un paquet software per l'intèrpret MAGMA. Aquest paquet ens proveeix d'eines per al tractament de codis binaris no necessàriament lineals.

Reconocimiento de objetos multi-clase basado en descriptores de forma

Este trabajo presenta un sistema para detectar y clasificar objetos binarios según la forma de éstos. En el primer paso del procedimiento, se aplica un filtrado para extraer el contorno del objeto. Con la información de los puntos de forma se obtiene un descriptor BSM con características altamente descriptivas, universales e invariantes. En la segunda fase del sistema se aprende y se clasifica la información del descriptor mediante Adaboost y Códigos Correctores de Errores. Se han usado bases de datos públicas, tanto en escala de grises como en color, para validar la implementación del sistema diseñado. Además, el sistema emplea una interfaz interactiva en la que diferentes métodos de procesamiento de imágenes pueden ser aplicados.

Codis Z2Z4-additius en Magma

En aquest projecte es presenta el desenvolupament d'un paquet d'aplicacions en l'entorn de programació matemàtica Magma, per al tractament dels codis anomenats Z2Z4-additius. Els codis Z2Z4-additius permeten representar alguns codis binaris, com a codis lineals en l'espai dels codis Z2Z4-additius. Aquest fet permetrà l'estudi de tota una sèrie de codis binaris no lineals que fins ara eren intractables.

Codis no lineals en MAGMA: construcció de codis perfectes

La finalitat d'aquest projecte és aconseguir construir codis binaris perfectes no lineals de manera eficient. Per a fer-ho, hem desenvolupat un paquet de software per a l'intèrpret MAGMA que conté funcions per a la construcció de codis perfectes, càlcul d'invariants de codis i altres funcions complementàries per a fer càlculs sobre les paraules d'un codi.

The analysis of approximate quickselect and related problems

Approximate Quickselect, a simple modification of the well known Quickselect algorithm for selection, can be used to efficiently find an element with rank k in a given range [i..j], out of n given elements. We study basic cost measures of Approximate Quickselect by computing exact and asymptotic results for the expected number of passes, comparisons and data moves during the execution of this algorithm. The key element appearing in the analysis of Approximate Quickselect is a trivariate recurrence that we solve in full generality. The general solution of the recurrence proves to be very useful, as it allows us to tackle several related problems, besides the analysis that originally motivated us. In particular, we have been able to carry out a precise analysis of the expected number of moves of the ith element when selecting the jth smallest element with standard Quickselect, where we are able to give both exact and asymptotic results. Moreover, we can apply our general results to obtain exact and asymptotic results for several parameters in binary search trees, namely the expected number of common ancestors of the nodes with rank i and j, the expected size of the subtree rooted at the least common ancestor of the nodes with rank i and j, and the expected distance between the nodes of ranks i and j.

Codis no lineals en Magma: noves construccions

L'objectiu principal d'aquest projecte és ampliar la llibreria BinaryCodes, iniciada al 2007, que ens permet construir i manipular codis binaris lineals i no lineals. Per aquest motiu, s'han desenvolupat una sèrie de funcions, amb els seus corresponents tests i exemples, en l'entorn de programació matemàtica Magma. Aquestes funcions consisteixen bàsicament en la construcció de nous codis a partir d'altres ja existents.

Generalized descriptive set theory and classification theory

Descriptive set theory is mainly concerned with studying subsets of the space of all countable binary sequences. In this paper we study the generalization where countable is replaced by uncountable. We explore properties of generalized Baire and Cantor spaces, equivalence relations and their Borel reducibility. The study shows that the descriptive set theory looks very different in this generalized setting compared to the classical, countable case. We also draw the connection between the stability theoretic complexity of first-order theories and the descriptive set theoretic complexity of their isomorphism relations. Our results suggest that Borel reducibility on uncountable structures is a model theoretically natural way to compare the complexity of isomorphism relations.

Emissió ràdio a baixa freqüència en fenòmens eruptius i en fonts esteses de raigs gamma d'alta i molt alta energia

La tasca investigadora presentada en aquesta memòria s'ha centrat en les fonts galàctiques de raigs gamma de molt alta energia LS I +61 303, HESS J1708-410 i HESS J1858+020. La primera és una binària de raigs gamma molt estudiada, formada per una estrella massiva i un objecte compacte. S'ha proposat un escenari on l'objecte compacte seria un púlsar jove, i la interacció del seu vent amb el vent de l'estrella generaria els raigs gamma. De totes formes, no s'ha detectat polsos procedents d'aquest putatiu púlsar. L'investigador va realitzar observacions en fase a 1280 MHz amb el radiotelescopi GMRT, sense trobar-hi polsos, cosa que implica un estricte límit superior de 0,38 mJy a la densitat mitjana de flux polsat en un putatiu púlsar amb un període major que 2 mil•lisegons en el sistema binari LS I +61 303. Per altra banda, HESS J1708-410 i HESS J1858+020 són dues fonts esteses de raigs gamma de molt alta energia de les quals no es coneix cap contrapart a d'altres longituds d'ona. L'investigador les va observar amb el GMRT, quatre vegades HESS J1708-410 (dues a 610 MHz i dues a 1400 MHz) i dues vegades HESS J1858+020 (una a cada freqüència). En les imatges realitzades amb aquestes dades no hi ha emissió estesa coincident amb les regions d'emissió de raigs gamma. HESS J1858+020 se solapa parcialment amb una font estesa que podria ser un SNR. De confirmar-se la falta de contrapartida ràdio de HESS J1708-410, estaríem parlant d'un accelerador hadrònic extraordinàriament eficient, d'una classe desconeguda fins ara.

Estructura de datos avanzadas : clases disjuntas, montículos, árboles de búsqueda

En aquest treball s'amplia la implementació en Java de les estructures de dades iniciada per Esteve Mariné, utilitzant el seu disseny bàsic. Concretament, s'ha fet la programació de les estructures de a) classes disjuntes, utilitzant els algorismes de llistes encadenades i amb estructura d'arbre, b) monticles, amb els algorismes binari, binomial i de Fibonacci, i c) arbres de recerca basats en l'algorisme d'arbre binari vermell-negre, el qual complementa els dos ja existents amb algorismes d'encadenaments i AVL. Per a examinar l'evolució de les estructures, s'ha preparat un visualitzador gràfic interactiu amb l'usuari que permet fer les operacions bàsiques de l'estructura. Amb aquest entorn és possible desar les estructures, tornar a reproduir-les i desfer i tornar a repetir les operacions fetes sobre l'estructura. Finalment, aporta una metodologia, amb visualització mitjançant gràfics, de l'avaluació comparativa dels algorismes implementats, que permet modificar els paràmetres d'avaluació com ara nombre d'elements que s'han de tractar, algorismes que s'han de comparar i nombre de repeticions. Les dades obtingudes es poden exportar per a analitzar-les posteriorment.

Compositional amalgamations and balances: a critical approach

The amalgamation operation is frequently used to reduce the number of parts of compositional data but it is a non-linear operation in the simplex with the usual geometry,the Aitchison geometry. The concept of balances between groups, a particular coordinate system designed over binary partitions of the parts, could be an alternative to theamalgamation in some cases. In this work we discuss the proper application of bothconcepts using a real data set corresponding to behavioral measures of pregnant sows

CoDa-dendrogram: A new exploratory too

The use of orthonormal coordinates in the simplex and, particularly, balance coordinates, has suggested the use of a dendrogram for the exploratory analysis of compositional data. The dendrogram is based on a sequential binary partition of a compositional vector into groups of parts. At each step of a partition, one group of parts isdivided into two new groups, and a balancing axis in the simplex between both groupsis defined. The set of balancing axes constitutes an orthonormal basis, and the projections of the sample on them are orthogonal coordinates. They can be represented in adendrogram-like graph showing: (a) the way of grouping parts of the compositional vector; (b) the explanatory role of each subcomposition generated in the partition process;(c) the decomposition of the total variance into balance components associated witheach binary partition; (d) a box-plot of each balance. This representation is useful tohelp the interpretation of balance coordinates; to identify which are the most explanatory coordinates; and to describe the whole sample in a single diagram independentlyof the number of parts of the sample

Generalized low-density codes with BCH constituents for full-diversity near-outage performance

A new graph-based construction of generalized low density codes (GLD-Tanner) with binary BCH constituents is described. The proposed family of GLD codes is optimal on block erasure channels and quasi-optimal on block fading channels. Optimality is considered in the outage probability sense. Aclassical GLD code for ergodic channels (e.g., the AWGN channel,the i.i.d. Rayleigh fading channel, and the i.i.d. binary erasure channel) is built by connecting bitnodes and subcode nodes via a unique random edge permutation. In the proposed construction of full-diversity GLD codes (referred to as root GLD), bitnodes are divided into 4 classes, subcodes are divided into 2 classes, and finally both sides of the Tanner graph are linked via 4 random edge permutations. The study focuses on non-ergodic channels with two states and can be easily extended to channels with 3 states or more.