Church-Rosser groups and growing context-sensitive groups

A finitely generated group is called a Church-Rosser group (growing context-sensitive group) if it admits a finitely generated presentation for which the word problem is a Church-Rosser (growing context-sensitive) language. Although the Church-Rosser languages are incomparable to the context-free languages under set inclusion, they strictly contain the class of deterministic context-free languages. As each context-free group language is actually deterministic context-free, it follows that all context-free groups are Church-Rosser groups. As the free abelian group of rank 2 is a non-context-free Church-Rosser group, this inclusion is proper. On the other hand, we show that there are co-context-free groups that are not growing context-sensitive. Also some closure and non-closure properties are established for the classes of Church-Rosser and growing context-sensitive groups. More generally, we also establish some new characterizations and closure properties for the classes of Church-Rosser and growing context-sensitive languages.

Computing Generators of Free Modules over Orders in Group Algebras

Let E be a number field and G be a finite group. Let A be any O_E-order of full rank in the group algebra E[G] and X be a (left) A-lattice. We give a necessary and sufficient condition for X to be free of given rank d over A. In the case that the Wedderburn decomposition E[G] \cong \oplus_xM_x is explicitly computable and each M_x is in fact a matrix ring over a field, this leads to an algorithm that either gives elements \alpha_1,...,\alpha_d \in X such that X = A\alpha_1 \oplus ... \oplusA\alpha_d or determines that no such elements exist. Let L/K be a finite Galois extension of number fields with Galois group G such that E is a subfield of K and put d = [K : E]. The algorithm can be applied to certain Galois modules that arise naturally in this situation. For example, one can take X to be O_L, the ring of algebraic integers of L, and A to be the associated order A(E[G];O_L) \subseteq E[G]. The application of the algorithm to this special situation is implemented in Magma under certain extra hypotheses when K = E = \IQ.

Uniformisierbarkeit in Familien von abelschen t-Moduln höheren Ranges

Diese Arbeit beschäftigt sich mit der Frage, wie sich in einer Familie von abelschen t-Moduln die Teilfamilie der uniformisierbaren t-Moduln beschreiben lässt. Abelsche t-Moduln sind höherdimensionale Verallgemeinerungen von Drinfeld-Moduln über algebraischen Funktionenkörpern. Bekanntermaßen lassen sich Drinfeld-Moduln in allgemeiner Charakteristik durch analytische Tori parametrisieren. Diese Tatsache überträgt sich allerdings nur auf manche t-Moduln, die man als uniformisierbar bezeichnet. Die Situation hat eine gewisse Analogie zur Theorie von elliptischen Kurven, Tori und abelschen Varietäten über den komplexen Zahlen. Um zu entscheiden, ob ein t-Modul in diesem Sinne uniformisierbar ist, wendet man ein Kriterium von Anderson an, das die rigide analytische Trivialität der zugehörigen t-Motive zum Inhalt hat. Wir wenden dieses Kriterium auf eine Familie von zweidimensionalen t-Moduln vom Rang vier an, die von Koeffizienten a,b,c,d abhängen, und gelangen dabei zur äquivalenten Fragestellung nach der Konvergenz von gewissen rekursiv definierten Folgen. Das Konvergenzverhalten dieser Folgen lässt sich mit Hilfe von Newtonpolygonen gut untersuchen. Schließlich erhält man durch dieses Vorgehen einfach formulierte Bedingungen an die Koeffizienten a,b,c,d, die einerseits die Uniformisierbarkeit garantieren oder andererseits diese ausschließen.

Root parametrized differential equations

The present thesis is about the inverse problem in differential Galois Theory. Given a differential field, the inverse  problem asks which linear algebraic groups can be realized as differential Galois groups of Picard-Vessiot extensions of this field.   In this thesis we will concentrate on the realization of the classical groups as differential Galois groups. We introduce a method for a very general realization of these groups. This means that we present for the classical groups of Lie rank $l$ explicit linear differential equations where the coefficients are differential polynomials in $l$ differential indeterminates over an algebraically closed field of constants $C$, i.e. our differential ground field is purely differential transcendental over the constants.   For the groups of type $A_l$, $B_l$, $C_l$, $D_l$ and $G_2$ we managed to do these realizations at the same time in terms of Abhyankar's program 'Nice Equations for Nice Groups'. Here the choice of the defining matrix is important. We found out that an educated choice of $l$ negative roots for the parametrization together with the positive simple roots leads to a nice differential equation and at the same time defines a sufficiently general element of the Lie algebra. Unfortunately for the groups of type $F_4$ and $E_6$ the linear differential equations for such elements are of enormous length. Therefore we keep in the case of $F_4$ and $E_6$ the defining matrix differential equation which has also an easy and nice shape.   The basic idea for the realization is the application of an upper and lower bound criterion for the differential Galois group to our parameter equations and to show that both bounds coincide. An upper and lower bound criterion can be found in literature. Here we will only use the upper bound, since for the application of the lower bound criterion an important condition has to be satisfied. If the differential ground field is $C_1$, e.g., $C(z)$ with standard derivation, this condition is automatically satisfied. Since our differential ground field is purely differential transcendental over $C$, we have no information whether this condition holds or not.   The main part of this thesis is the development of an alternative lower bound criterion and its application. We introduce the specialization bound. It states that the differential Galois group of a specialization of the parameter equation is contained in the differential Galois group of the parameter equation. Thus for its application we need a differential equation over $C(z)$ with given differential Galois group. A modification of a result from Mitschi and Singer yields such an equation over $C(z)$ up to differential conjugation, i.e. up to transformation to the required shape. The transformation of their equation to a specialization of our parameter equation is done for each of the above groups in the respective transformation lemma.

Model Selection in Summary Evaluation

A difficulty in the design of automated text summarization algorithms is in the objective evaluation. Viewing summarization as a tradeoff between length and information content, we introduce a technique based on a hierarchy of classifiers to rank, through model selection, different summarization methods. This summary evaluation technique allows for broader comparison of summarization methods than the traditional techniques of summary evaluation. We present an empirical study of two simple, albeit widely used, summarization methods that shows the different usages of this automated task-based evaluation system and confirms the results obtained with human-based evaluation methods over smaller corpora.

On Degeneracy of Linear Reconstruction from Three Views: Linear Line Complex and Applications

This paper investigates the linear degeneracies of projective structure estimation from point and line features across three views. We show that the rank of the linear system of equations for recovering the trilinear tensor of three views reduces to 23 (instead of 26) in the case when the scene is a Linear Line Complex (set of lines in space intersecting at a common line) and is 21 when the scene is planar. The LLC situation is only linearly degenerate, and we show that one can obtain a unique solution when the admissibility constraints of the tensor are accounted for. The line configuration described by an LLC, rather than being some obscure case, is in fact quite typical. It includes, as a particular example, the case of a camera moving down a hallway in an office environment or down an urban street. Furthermore, an LLC situation may occur as an artifact such as in direct estimation from spatio-temporal derivatives of image brightness. Therefore, an investigation into degeneracies and their remedy is important also in practice.

Regression analysis of compositional data when both the dependent variable and independent variable are components

It is well known that regression analyses involving compositional data need special attention because the data are not of full rank. For a regression analysis where both the dependent and independent variable are components we propose a transformation of the components emphasizing their role as dependent and independent variables. A simple linear regression can be performed on the transformed components. The regression line can be depicted in a ternary diagram facilitating the interpretation of the analysis in terms of components. An exemple with time-budgets illustrates the method and the graphical features

Scoring Methods for Ordinal Multidimensional Forced-Choice Items

In most psychological tests and questionnaires, a test score is obtained by taking the sum of the item scores. In virtually all cases where the test or questionnaire contains multidimensional forced-choice items, this traditional scoring method is also applied. We argue that the summation of scores obtained with multidimensional forced-choice items produces uninterpretable test scores. Therefore, we propose three alternative scoring methods: a weak and a strict rank preserving scoring method, which both allow an ordinal interpretation of test scores; and a ratio preserving scoring method, which allows a proportional interpretation of test scores. Each proposed scoring method yields an index for each respondent indicating the degree to which the response pattern is inconsistent. Analysis of real data showed that with respect to rank preservation, the weak and strict rank preserving method resulted in lower inconsistency indices than the traditional scoring method; with respect to ratio preservation, the ratio preserving scoring method resulted in lower inconsistency indices than the traditional scoring method

Robust Factor Analysis for Compositional Data

Factor analysis as frequent technique for multivariate data inspection is widely used also for compositional data analysis. The usual way is to use a centered logratio (clr) transformation to obtain the random vector y of dimension D. The factor model is then y = Λf + e (1) with the factors f of dimension k < D, the error term e, and the loadings matrix Λ. Using the usual model assumptions (see, e.g., Basilevsky, 1994), the factor analysis model (1) can be written as Cov(y) = ΛΛT + ψ (2) where ψ = Cov(e) has a diagonal form. The diagonal elements of ψ as well as the loadings matrix Λ are estimated from an estimation of Cov(y). Given observed clr transformed data Y as realizations of the random vector y. Outliers or deviations from the idealized model assumptions of factor analysis can severely effect the parameter estimation. As a way out, robust estimation of the covariance matrix of Y will lead to robust estimates of Λ and ψ in (2), see Pison et al. (2003). Well known robust covariance estimators with good statistical properties, like the MCD or the S-estimators (see, e.g. Maronna et al., 2006), rely on a full-rank data matrix Y which is not the case for clr transformed data (see, e.g., Aitchison, 1986). The isometric logratio (ilr) transformation (Egozcue et al., 2003) solves this singularity problem. The data matrix Y is transformed to a matrix Z by using an orthonormal basis of lower dimension. Using the ilr transformed data, a robust covariance matrix C(Z) can be estimated. The result can be back-transformed to the clr space by C(Y ) = V C(Z)V T where the matrix V with orthonormal columns comes from the relation between the clr and the ilr transformation. Now the parameters in the model (2) can be estimated (Basilevsky, 1994) and the results have a direct interpretation since the links to the original variables are still preserved. The above procedure will be applied to data from geochemistry. Our special interest is on comparing the results with those of Reimann et al. (2002) for the Kola project data

Plan de negocio para la comercialización de un producto innovador de cuidado personal en el mercado colombiano

Las relaciones comerciales entre países del mundo han venido aumentando recientemente, mejorando a través de tratados y acuerdos, entre estos países. China ha sido una potencia económica fuerte en sus relaciones comerciales y de negocios establecidos con países del mundo. En lo que a Colombia se refiere, se han venido planteando posibles negociaciones para el logro de acuerdos en un futuro cercano que permitan un intercambio libre de productos y servicios. Aprovechando las relaciones entre estos países surge la idea de un negocio para la importación de un producto chino novedoso orientado al sector de belleza en Colombia. Este producto es un aparato electrotérmico inalámbrico, el cual aun no existe en el mercado colombiano, razón por la cual podría tener una muy buena aceptación por parte de la mujer colombiana, pues es un producto que le permitirá ahorrar tiempo y eliminar la dependencia al uso de una toma corriente para utilizar este aparato electrotérmico. Para evaluar la factibilidad de negocio, se realizo un estudio de mercado del cual se obtuvieron buenos resultados, pues un porcentaje alto aceptaron que comprarían este producto al precio que esta dentro del rango del precio de venta en Colombia. Se estudiaron también las inversiones necesarias para iniciar el negocio y los costos de funcionamiento de este. Se realizo una proyección a cinco años del funcionamiento del negocio, y los resultados de este fueron que la empresa siempre tendrá liquidez para solventarse en el transcurso de estos cinco años. Para realizar la inversión inicial del negocio se requiere capital de los socios y obtención de un crédito por parte de estos. Un crédito que será pagado en su totalidad en el tercer año. Se realizo el cálculo del costo de venta del producto para determinar su precio final el cual, no resultó mayor al promedio de los aparatos electrotérmicos actuales del mercado con el valor agregado que el producto que se pretende importar es inalámbrico. Lo anterior es una ventaja del producto del mercado, junto con la garantía y calidad que se pretende tener en este producto. Dado que el negocio el viable, según lo descrito anteriormente, se investigaron los papeles y costos necesarios en cámara y comercio para la constitución de una empresa.

Enhanced Model Selection for motion segmentation

In this paper a novel rank estimation technique for trajectories motion segmentation within the Local Subspace Affinity (LSA) framework is presented. This technique, called Enhanced Model Selection (EMS), is based on the relationship between the estimated rank of the trajectory matrix and the affinity matrix built by LSA. The results on synthetic and real data show that without any a priori knowledge, EMS automatically provides an accurate and robust rank estimation, improving the accuracy of the final motion segmentation

Es el reimplante valvular mejor que el bentall biológico modificado para tratar aneurismas de la raíz asociados a insuficiencia?

Es el reimplante valvular mejor que el Bentall Biológico Modificado para tratar aneurismas de la raíz asociados a insuficiencia? Obando CE; Gutiérrez HF; Santamaría G, Bresciani R; Camacho J; Sandoval N; Umaña J. Departamento de Cirugía Cardiovascular, Fundación Cardio Infantil, Bogotá, Colombia. Objetivo: comparar resultados funcionales, morbilidad y sobrevida a corto y mediano plazo, tras la realización de Bentall modificado con prótesis Freestyle vs reimplante valvular de Tirone David, en insuficiencia aortica secundaria a aneurisma de la raíz. Diseño: revisión de registros institucionales de 88 pacientes tratados entre enero de 2003 y agosto de 2009 con insuficiencia aortica secundaria a aneurisma de la raíz sin daño valvular, distribuidos en dos cohortes: Grupo 1 (Bentall modificado) y Grupo 2 (reimplante valvular). Se evaluaron complicaciones perioperatorias, transfusiones, estancias hospitalarias y en el seguimiento a mediano plazo insuficiencia valvular, clase funcional, función ventricular y sobrevida. Solidez de los resultados verificada mediante análisis de propensidad con balanceo de grupos. Resultados: Grupo (1) 51(57.9%) pacientes y grupo (2) 37(42.1%). Aunque el grupo 2 es mas joven, patrones similares de coomorbilidad, anatomía de la raíz, función y diámetros ventriculares hacen comparables los dos grupos. Seguimiento de 3.3 años (IQR 2.0-4.4). Mortalidad temprana 2(3.8%) vs 0 p =0.2 y tardía de 2(4.1%) vs 0 p=0.33. El análisis estratificado de covariables en bloques de distribución tampoco identifica diferencias en mortalidad. El análisis de sobrevida de mortalidad y sobrevida libre de eventos identifica desenlaces similares entre los grupos (Log-Rank chi2=0.9, p=0.3); incluyendo Insuficiencia aortica = II temprana (3.8% vs 0, p=0.2) y tardía (3.8%vs 0, p=0.1), transfusiones perioperatorias, reintervenciones por sangrado (2.3% vs 3.4%, p=0.4), arritmias (25.5% vs 13.5%, p=0.2) y disfunción neurológica (5.7% vs 2.9%, p=0.9). Finalmente la hospitalización total (6.5 {1-35} vs 4{3-16} p=0.001) y estancia en Cuidado intensivo (2.5 {1-21} vs 1{1-16} p=0.001) es superior en el grupo1. Conclusiones: el tratamiento de los aneurismas de la raíz aortica asociados a insuficiencia valvular sin daño estructural, mediante reimplante valvular o Bentall biológico modificado ofrece resultados similares a corto y mediano plazo. La preservación valvular se asocia a estancias mas cortas, pero no hay diferencia en complicaciones postoperatorias, estatus funcional, insuficiencia valvular, función ventricular, mortalidad y sobrevida libre de eventos adversos.

Parámetros cuantitativos de la resonancia magnética cerebral en esclerosis múltiple y su correlación con la discapacidad

A pesar del amplio uso de la resonancia magnética en la esclerosis múltiple no se ha logrado una adecuada correlación clínico-imagenológica en esta enfermedad. Objetivo: Determinar la correlación del volumen normalizado de sustancia gris y del volumen de lesiones hipointensas en T1 obtenidos a partir de la resonancia magnética cerebral con la escala de discapacidad extendida en pacientes con diagnóstico de esclerosis múltiple. Materiales y métodos: Estudio retrospectivo en pacientes con diagnóstico de esclerosis múltiple de la Fundación Cardioinfantil. Se obtuvieron los resultados de la escala de discapacidad expandida así como análisis cuantitativo de las imágenes correspondientes de resonancia magnética por medio de la herramienta SIENA. Se cuantificaron el volumen del parénquima cerebral, sustancia gris, sustancia blanca y volumen de lesiones hipointensas en T1. Posteriormente, se relacionaron estos resultados con la escala de discapacidad extendida de Kurtzke previamente obtenida. Para el análisis estadístico se emplearon el test correlación de Spearman y t de Student y Hotelling. Resultados: Se incluyeron 58 pacientes, encontrándose correlaciones estadísticamente significativas entre la escala de discapacidad extendida y volumen de parénquima cerebral, volumen de sustancia gris y volumen de lesiones hipointensas en T1; de 0.384, 0.386 y 0.39. No se encontró una relación entre el volumen de sustancia blanca y la escala de discapacidad. Conclusiones: Existe una correlación clínico-imagenológica moderada en la esclerosis múltiple. La cuantificación de los parámetros propuestos en este estudio podría ser utilizada como herramienta en el seguimiento de la enfermedad y monitorización de nuevos tratamientos.

Web Graph

Slides and an essay on the Web Graph, search engines and how Google calculates Page Rank

Resolución espontánea de reflujo vesicoureteral primario en niños: factores predictores y nomograma de predicción

Introducción: Determinamos la proporción de resolución espontánea de RVU primario en una población de niños menores de 5 años así como los factores que influyen y predicen tal resolución, con base en lo cual diseñamos un nomograma que permite determinar la posibilidad de resolución espontánea de cada grado de reflujo a los 3 años de su diagnóstico Metodología: Incluimos 407 niños con diagnóstico de RVU primario en un periodo de 10 años. Mediante análisis de asociación y comparaciones de promedios se determinaron las variables que se comportaron como factores de riesgo para fallar en obtener resolución espontanea y por un modelo de regresión logística binomial se confirmaron asociaciones. Se practicaron comparaciones mediante ANOVA o t-test y así como análisis de sobrevida mediante Log Rank Test para determinar las variables que influían también en el tiempo necesario para obtener resolución espontánea. Resultados: Las tasas de resolución espontánea fueron 92%, 85%, 56.4%, 21% y 5% para los grados I a V de reflujo respectivamente. En el análisis multivariado, Las variables nefropatía por reflujo (sig=0,000), Síndrome de evacuación disfuncional (SED) (sig=0,000) y bilateralidad (sig=0,006) fueron los factores de riesgo independientes para la falla del RVU en resolver espontáneamente. Sin embargo, en los análisis de sobrevida solo la variable SED demostró influir en el tiempo necesario para obtener resolución espontanea (sig=0,002). Discusión: Los hallazgos de este estudio ratifican la importancia de incluir variables como SED, nefropatía por reflujo y lateralidad en los modelos de predicción de resolución espontánea del RVU.