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.

Análisis textual y discursivo de dos relatos del posmodernismo mexicano en la segunda mitad del siglo XX: Nuevas fronteras del género a través de la experimentación intertextual y metaficcional.

La labor principal del presente trabajo de investigación consiste en el análisis de dos relatos del “posmodernismo mexicano” de la segunda mitad del siglo XX. Para ello, y en primer lugar, se parte de la acotación y definición de términos y nociones ligados a la “posmodernidad”, el “posmodernismo” y “lo posmoderno”. En segundo lugar, se lleva a cabo una lectura crítica de propuestas teóricas de autores como Fredric Jameson y Lauro Zavala, destinadas a describir fenómenos y prácticas relacionadas con la posmodernidad como forma discursiva y del relato posmoderno mexicano, respectivamente. En último término, se analizan los relatos mencionados bajo dos aspectos principales de experimentación: la intertextualidad y la metaficcionalidad y de los cuales se desprenden fenómenos privilegiados como “la hibridación genérica”, “el uso del pastiche”, “la superposición de códigos narrativos”, “la fragmentación del tiempo”, así como toda una serie de estrategias discursivas destinadas a expandir las fronteras del género relato en el contexto de enunciación mencionado.

Language knowledge and earnings in Catalonia

In this paper we are aimed to investigate the relationship between Catalan knowledge and individual earnings in Catalonia. Using data from 2006, we find a positive earning return to Catalan proficiency; however, when accounting for self-selection into Catalan knowledge, we find a higher language return (20% of extra earnings), suggesting that individuals who are more prone to know Catalan are also less remunerated than others (negative selection effect). Moreover, we also find important complementarities between language knowledge and completed education, which means that only more educated individuals benefit from Catalan knowledge.

Language knowledge and earnings in Catalonia

This paper investigates the economic value of Catalan knowledge for national and foreign first- and second-generation immigrants in Catalonia. Specifically, drawing on data from the “Survey on Living Conditions and Habits of the Catalan Population (2006)”, we want to quantify the expected earnings differential between individuals who are proficient in Catalan and those who are not, taking into account the potential endogeneity between knowledge of Catalan and earnings. The results indicate the existence of a positive return to knowledge of Catalan, with a 7.5% increase in earnings estimated by OLS; however, when we account for the presence of endogeneity, monthly earnings are around 18% higher for individuals who are able to speak and write Catalan. However, we also find that language and education are complementary inputs for generating earnings in Catalonia, given that knowledge of Catalan increases monthly earnings only for more educated individuals.

L'ús dels clítics pronominals del català i la seva adquisició per parlants de romanès i de tagal

El nostre estudi ha analitzat els mecanismes de transferència de la L1 en dos grups de parlants, un que té el romanès i l’altre el tagal com a llengües mare, en el procés d’aprenentatge del català com a L2. En concret ens hem centrat en l’estudi de l’ús dels clítics pronominals, una de les parts de la gramàtica catalana més apassionant per les seves idiosincràsies i la seva diversitat formal. L’ús d’aquest tipus de pronoms és un aspecte que resulta complicat d’adquirir per parlants de llengües en què no existeixen o on l’ús que en fan és diferent. En el nostre estudi, ens hem basat inicialment en la descripció de les característiques fonamentals dels clítics pronominals del català, del romanès i del tagal, a partir de bibliografia especialitzada i més general, i, en el cas del català, fent servir també la pròpia competència. Després d’aquest apartat més descriptiu, hem utilitzat un corpus d’entrevistes fetes en català a dos grups de parlants, el primer amb aprenents de català que tenen el romanès com a L1 i el segon amb aprenents de català que tenen el tagal com a L1, per analitzar quantitativament i qualitativament l’ús dels clítics pronominals. Un altre grup d’entrevistes, aquesta vegada a persones autòctones (català L1), ens ha servit com a grup de control. El nostre estudi dóna suport a la hipòtesi que atorga una importància especial a la transferència de la L1 en l’adquisició d'una segona llengua en general, i en la dels clítics pronominals d’una llengua romànica, en particular. Els resultats mostren que hi ha diferències entre els dos grups d'aprenents que són estadísticament significatives (ús del programa SPSS) i poden ser atribuïdes a les característiques de la L1.

Creació d’un programari per a l’avaluació de la qualitat dels resultats analítics generats al laboratori

La validació de mètodes és un dels pilars fonamentals de l’assegurament de la qualitat en els laboratoris d’anàlisi, tal i com queda reflectit en la norma ISO/IEC 17025. És, per tant, un aspecte que cal abordar en els plans d’estudis dels presents i dels futurs graus en Química. Existeix molta bibliografia relativa a la validació de mètodes, però molt sovint aquesta s’utilitza poc, degut a la dificultat manifesta de processar tota la informació disponible i aplicar-la al laboratori i als problemes concrets. Una altra de les limitacions en aquest camps és la manca de programaris adaptats a les necessitats del laboratori. Moltes de les rutines estadístiques que es fan servir en la validació de mètodes són adaptacions fetes amb Microsoft Excel o venen incorporades en paquets estadístics gegants, amb un alt grau de complexitat. És per aquest motiu que l’objectiu del projecte ha estat generar un programari per la validació de mètodes i l’assegurament de la qualitat dels resultats analítics, que incorporés únicament les rutines necessàries. Específicament, el programari incorpora les funcions estadístiques necessàries per a verificar l’exactitud i avaluar la precisió d’un mètode analític. El llenguatge de programació triat ha estat el Java en la seva versió 6. La part de creació del programari ha constat de les següents etapes: recollida de requisits, anàlisi dels requisits, disseny del programari en mòduls, programació d les funcions del programa i de la interfície gràfica, creació de tests d’integració i prova amb usuaris reals, i, finalment, la posada en funcionament del programari (creació de l’instal·lador i distribució del programari).

Strong isomorphism reductions in complexity theory

We give the first systematic study of strong isomorphism reductions, a notion of reduction more appropriate than polynomial time reduction when, for example, comparing the computational complexity of the isomorphim problem for different classes of structures. We show that the partial ordering of its degrees is quite rich. We analyze its relationship to a further type of reduction between classes of structures based on purely comparing for every n the number of nonisomorphic structures of cardinality at most n in both classes. Furthermore, in a more general setting we address the question of the existence of a maximal element in the partial ordering of the degrees.

sisCave : Sistema de Catalogació de Cavitats

Aquest treball de final de carrera pretén cobrir una necessitat divulgativa del món de l'espeleologia, proporcionant al col·lectiu espeleològic una aplicació basada en web que permeti publicar, de forma cooperativa, ressenyes de cavitats incorporant dades textuals, fotografies, topografies i mapes d'ubicació.El projecte s'ha desenvolupat com a Treball de Final de Carrera de l'àrea J2EE de l'Enginyeria Tècnica en Informàtica de Gestió. La seva implementació, per tant, està basada en Programació Orientada a Objectes amb llenguatge Java i tecnologies J2EE.

Semàntica del mot : propietats semàntiques de tres verbs de desplaçament

El treball té com a objectiu l'estudi de les propietats semàntiques d'un grup de verbs de desplaçament i els seus corresponents arguments. La informació sobre el tipus de complement que demana cada verb és important de cara a conèixer l'estructura sintàctica de la frase i oferir solucions pràctiques en tasques de Processament del Llenguatge Natural. L'anàlisi se centrarà en els verbs conduir, navegar i volar, a partir dels sentits bàsics que el Diccionari d'ús dels verbs catalans (DUVC) descriu per a cadascun d'aquests verbs i de les seves restriccions selectives. Comprovarem, mitjançant un centenar de frases extretes del Corpus d'Ús del Català a la Web de la Universitat Pompeu Fabra i del Corpus Textual Informatitzat de la Llengua Catalana de l'Institut d'Estudis Catalans, si en la llengua es donen només els sentits i usos descrits en el DUVC i quins són els més freqüents. Finalment, descriurem els noms que fan de nucli dels arguments en termes de trets semàntics.

Mètodes empírics en lingüística cognitiva

Peer-reviewed

Gènere i bilingüisme: connectant experiències i teories. Introductory paper in Santaemilia, José, Patricia Bou, Sergio Maruenda i Gora Zaragoza International Perspectives on Gender and Language

Peer-reviewed

Shape complexity based on mutual information

Shape complexity has recently received attention from different fields, such as computer vision and psychology. In this paper, integral geometry and information theory tools are applied to quantify the shape complexity from two different perspectives: from the inside of the object, we evaluate its degree of structure or correlation between its surfaces (inner complexity), and from the outside, we compute its degree of interaction with the circumscribing sphere (outer complexity). Our shape complexity measures are based on the following two facts: uniformly distributed global lines crossing an object define a continuous information channel and the continuous mutual information of this channel is independent of the object discretisation and invariant to translations, rotations, and changes of scale. The measures introduced in this paper can be potentially used as shape descriptors for object recognition, image retrieval, object localisation, tumour analysis, and protein docking, among others

Error and complexity of random walk Monte Carlo radiosity

The author studies the error and complexity of the discrete random walk Monte Carlo technique for radiosity, using both the shooting and gathering methods. The author shows that the shooting method exhibits a lower complexity than the gathering one, and under some constraints, it has a linear complexity. This is an improvement over a previous result that pointed to an O(n log n) complexity. The author gives and compares three unbiased estimators for each method, and obtains closed forms and bounds for their variances. The author also bounds the expected value of the mean square error (MSE). Some of the results obtained are also shown

The interactional space in CLIL (Content and Language Integrated Learning) and EFL (English as a Foreign Language) classrooms

Aquest estudi pretén investigar els intercanvis verbals mestre/a – aprenent(s) en dos contextos d'instrucció diferents: classes amb un enfocament AICLE (Aprenentatge Integrat de Continguts Curriculars i Llengua Estrangera) on s’aprenen continguts no lingüístics a través de l’anglès, per una banda, i classes 'tradicionals' d'anglès com a llengua estrangera, on l’anglès és alhora objecte d’estudi i vehicle de comunicació, per una altra banda. Més concretament, les preguntes que formula el/la mestre/a, la producció oral dels aprenents i el 'feedback' del/de la mestre/a en els episodis d’atenció a la forma s’han estudiat a la llum de les principals teories provinents del camp de l’Adquisició de Segones Llengües (SLA) per tal de demostrar el seu paper en l’aprenentatge de l’anglès. El corpus de dades prové de l’enregistrament de 7 sessions AICLE i d'11 sessions EFL enregistrades en format àudio i vídeo en dos centres públics d’Educació Primària (EP) de Catalunya. A cadascuna de les escoles, el/la mateix/a mestre/a és l’encarregat/da dels dos tipus d’instrucció amb el mateix grup d’aprenents (10-11 anys d’edat), fet que permet eliminar variables individuals com l'aptitud dels aprenents o l'estil del/de la mestre/a.Els resultats mostren un cert nombre de similituds discursives entre AICLE i EFL donat que ambdós enfocaments tenen lloc en el context-classe amb unes característiques ben definides. Tal com apunta la recerca realitzada en aquest camp, la instrucció AICLE reuneix un seguit de condicions idònies per un major desenvolupament dels nivells de llengua anglesa més enllà de les classes ‘tradicionals’ d’anglès. Malgrat això, aquest estudi sembla indicar que el potencial d'AICLE pel que fa a facilitar una exposició rica a l’anglès i una producció oral significativa no s’explota degudament. En aquest sentit, els resultats d’aquest estudi poden contribuir a la formació dels futurs professors d'AICLE si es busca l’assoliment d’una complementarietat d’ambdós contextos amb l’objectiu últim de millorar els nivells de domini de la llengua anglesa.