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."

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.

Analyzing complexity in foreign language monologic oral production in a CLIL context

The study tested three analytic tools applied in SLA research (T-unit, AS-unit and Idea-unit) against FL learner monologic oral data. The objective was to analyse their effectiveness for the assessment of complexity of learners' academic production in English. The data were learners' individual productions gathered during the implementation of a CLIL teaching sequence on Natural Sciences in a Catalan state secondary school. The analysis showed that only AS-unit was easily applicable and highly effective in segmenting the data and taking complexity measures

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.

Métodos automatizados de segmentación para cuantificar el grosor cortical en RM en pacientes con deterioro cognitivo y enfermedad de Parkinson

El objetivo del presente estudio es encontrar la relación que existe entre los síntomas de deterioro cognitivo y el grosor cortical cerebral en una muestra de 45 pacientes con Enfermedad de Parkinson diagnosticados y tratados en la consulta externa del Servicio de Neurología del Hospital de la Santa Creu i Sant Pau de Barcelona, quienes fueron sometidos a tests neuropsicológicos que evaluaban su función mental y motora y a quienes se les realizó un estudio de Resonancia Magnética 3 Tesla para evaluar, mediante técnicas de postprocesados, su grosor cortical. Los resultados demostraron una clara disminución del grosor cortical en determinadas áreas que se correlacionaban con las funciones cognitivas afectadas en estos pacientes.

Cortical mapping of the neuronal circuits modulating the muscle tone. Introduction to the electrophysiological treatment of the spastic hand.

L’objectiu d’aquest estudi es investigar l’organització cortical junt amb la connectivitat còrtico-subcortical en subjectes sans, com a estudi preliminar. Els mapes corticals s’han fet per TMS navegada, i els punts motors obtinguts s’han exportant per estudi tractogràfic i anàlisi de las seves connexions. El coneixement precís de la localització de l’àrea cortical motora primària i les seves connexions es la base per ser utilitzada en estudis posteriors de la reorganització cortical i sub-cortical en pacients amb infart cerebral. Aquesta reorganització es deguda a la neuroplasticitat i pot ser influenciada per els efectes neuromoduladors de la estimulació cerebral no invasiva.

Influence of the in vivo deregulation of the expression of ntrk3 (trkc) on cortical development of a murine model of panic/anxiety disorder

Alteracions durant el desenvolupament cerebral produirien canvis en la connectivitat neuronal i la bioquímica cel•lular que podrien resultar en una disfunció cognitiva i/o emocional, desembocant a trastorns psiquiàtrics. Les neurotrofines intervenen en els processos del neurodesenvolupament i en la funcionalitat del cervell adult i, conseqüentment, serien bons candidats com a factors de predisposició en diverses malalties mentals. S’ha suggerit la implicació del receptor de la neurotrofina 3, TrkC, en el trastorn de pànic. Nosaltres proposem que la sobreexpressió del gen NTRK3 (TrkC) és un mediador comú dels desencadenants genètics i ambientals d’aquest trastorn. Concretament, la seva desregulació podria produir canvis estructurals i funcionals a l’escorça cerebral dels pacients pel seu paper durant l’establiment dels circuïts corticals i la neuroplasticitat a l’adult, probablement esdevenint elements de predisposició a patir atacs de pànic. Els objectius principals d’aquest treball han estat: 1/determinar la contribució específica del gen NTRK3 a les alteracions de l’escorça cerebral observades en pacients, utilitzant un model murí modificat genèticament (TgNTRK3), i 2/analitzar l’impacte específic de la sobreexpressió de NTRK3 sobre la corticogènesi durant estadis embrionaris o postnatals estudiant la neurogènesi i la neuritogènesi. Els resultats indiquen que la sobreexpressió de NTRK3 als ratolins produeix una reducció del gruix de l’escorça frontal, recapitulant la hipofrontalitat dels pacients, que comportaria una menor inhibició dels nuclis subcorticals del sistema límbic com l’amígdala, i alteracions citoarquitectòniques a l’escorça prefrontal medial que recolzen la hipòtesi del seu mal funcionament. Tanmateix, els ratolins TgNTRK3 presenten canvis estructurals a l’escorça somatosensorial, suggerint que el processament de la informació sensorial podria estar alterat, el que encara no s’ha explorat en pacients. La sobreexpressió de NTRK3 també afecta la neuritogènesi en cultius primaris corticals i modifica la resposta de les neurones a l’estimulació amb neurotrofines. Per tant, el fenotip cortical adult dels TgNTRK3 podria dependre d’alteracions durant la corticogènesi.

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

Impaired fast-spiking, suppressed cortical inhibition and increased susceptibility to seizures in mice lacking Kv3.2 K+ channel proteins

Voltage-gated K+ channels of the Kv3 subfamily have unusual electrophysiological properties, including activation at very depolarized voltages (positive to −10 mV) and very fast deactivation rates, suggesting special roles in neuronal excitability. In the brain, Kv3 channels are prominently expressed in select neuronal populations, which include fast-spiking (FS) GABAergic interneurons of the neocortex, hippocampus, and caudate, as well as other high-frequency firing neurons. Although evidence points to a key role in high-frequency firing, a definitive understanding of the function of these channels has been hampered by a lack of selective pharmacological tools. We therefore generated mouse lines in which one of the Kv3 genes, Kv3.2, was disrupted by gene-targeting methods. Whole-cell electrophysiological recording showed that the ability to fire spikes at high frequencies was impaired in immunocytochemically identified FS interneurons of deep cortical layers (5-6) in which Kv3.2 proteins are normally prominent. No such impairment was found for FS neurons of superficial layers (2-4) in which Kv3.2 proteins are normally only weakly expressed. These data directly support the hypothesis that Kv3 channels are necessary for high-frequency firing. Moreover, we found that Kv3.2 −/− mice showed specific alterations in their cortical EEG patterns and an increased susceptibility to epileptic seizures consistent with an impairment of cortical inhibitory mechanisms. This implies that, rather than producing hyperexcitability of the inhibitory interneurons, Kv3.2 channel elimination suppresses their activity. These data suggest that normal cortical operations depend on the ability of inhibitory interneurons to generate high-frequency firing.

On high-rate full-diversity 2x2 space-time codes with low-complexity optimum detection

The 2×2 MIMO profiles included in Mobile WiMAX specifications are Alamouti’s space-time code (STC) fortransmit diversity and spatial multiplexing (SM). The former hasfull diversity and the latter has full rate, but neither of them hasboth of these desired features. An alternative 2×2 STC, which is both full rate and full diversity, is the Golden code. It is the best known 2×2 STC, but it has a high decoding complexity. Recently, the attention was turned to the decoder complexity, this issue wasincluded in the STC design criteria, and different STCs wereproposed. In this paper, we first present a full-rate full-diversity2×2 STC design leading to substantially lower complexity ofthe optimum detector compared to the Golden code with only a slight performance loss. We provide the general optimized form of this STC and show that this scheme achieves the diversitymultiplexing frontier for square QAM signal constellations. Then, we present a variant of the proposed STC, which provides a further decrease in the detection complexity with a rate reduction of 25% and show that this provides an interesting trade-off between the Alamouti scheme and SM.

Excuse me, but your accent is very unusual. The complexity of establishing third languages in Inglourious Basterds. Applying a model of translation analysis to dubbing

The growing multilingual trend in movie production comes with a challenge for dubbing translators since they are increasingly confronted with more than one source language. The main purpose of this master’s thesis is to provide a case study on how these third languages (see CORRIUS and ZABALBEASCOA 2011) are rendered. Another aim is to put a particular focus on their textual and narrative functions and detect possible shifts that might occur in translations. By applying a theoretical model for translation analysis (CORRIUS and ZABALBEASCOA 2011), this study describes how third languages are rendered in the German, Spanish, and Italian dubbed versions of the 2009 Tarantino movie Inglourious Basterds. A broad range of solution-types are thereby revealed and prevalent restrictions of the translation process identified. The target texts are brought in context with some sociohistorical aspects of dubbing in order to detect prevalent norms of the respective cultures andto discuss the acceptability of translations (TOURY 1995). The translatability potential of even highly complex multilingual audiovisual texts is demonstrated in this study. Moreover, proposals for further studies in multilingual audiovisual translation are outlined and the potential for future investigations in this field thereby emphasised.

Organisational Values as "Attractors of Chaos": An Emerging Cultural Change to Manage Organisational Complexity

Business organisations are excellent representations of what in physics and mathematics are designated "chaotic" systems. Because a culture of innovation will be vital for organisational survival in the 21st century, the present paper proposes that viewing organisations in terms of "complexity theory" may assist leaders in fine-tuning managerial philosophies that provide orderly management emphasizing stability within a culture of organised chaos, for it is on the "boundary of chaos" that the greatest creativity occurs. It is argued that 21st century companies, as chaotic social systems, will no longer be effectively managed by rigid objectives (MBO) nor by instructions (MBI). Their capacity for self-organisation will be derived essentially from how their members accept a shared set of values or principles for action (MBV). Complexity theory deals with systems that show complex structures in time or space, often hiding simple deterministic rules. This theory holds that once these rules are found, it is possible to make effective predictions and even to control the apparent complexity. The state of chaos that self-organises, thanks to the appearance of the "strange attractor", is the ideal basis for creativity and innovation in the company. In this self-organised state of chaos, members are not confined to narrow roles, and gradually develop their capacity for differentiation and relationships, growing continuously toward their maximum potential contribution to the efficiency of the organisation. In this way, values act as organisers or "attractors" of disorder, which in the theory of chaos are equations represented by unusually regular geometric configurations that predict the long-term behaviour of complex systems. In business organisations (as in all kinds of social systems) the starting principles end up as the final principles in the long term. An attractor is a model representation of the behavioral results of a system. The attractor is not a force of attraction or a goal-oriented presence in the system; it simply depicts where the system is headed based on its rules of motion. Thus, in a culture that cultivates or shares values of autonomy, responsibility, independence, innovation, creativity, and proaction, the risk of short-term chaos is mitigated by an overall long-term sense of direction. A more suitable approach to manage the internal and external complexities that organisations are currently confronting is to alter their dominant culture under the principles of MBV.