The word problem distinguishes counter languages

Counter automata are more powerful versions of finite state automata where addition and subtraction operations are permitted on a set of n integer registers, called counters. We show that the word problem of Zn is accepted by a nondeterministic m-counter automaton if and only if m &= n.

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.

Addressing the net balances problem as a prerequisite for EU budget reform: a proposal

Conflict among member states regarding the distribution of net financial burdens has been allowed to contaminate the entire design of the EU budget with very negative consequences in terms of equity, efficiency and transparency. To get around this problem and pave the way for a substantive budget reform, we propose to decouple distributional negotiations from the rest of the budget process by linking member state net balances in a rigid manner to relative prosperity. This would be achieved through the introduction of a system of compensating horizontal transfers that would take to its logical conclusion the Commission's proposal for a generalized compensation mechanism. We discuss the impact of the proposed scheme on member states? incentives and illustrate its financial implications using revenue and expenditure projections for 2013 that are based on the current Financial Perspectives and Own Resources Decision.

Label Space Reduction in All-Optical Label Switchiing Networks

Report for the scientific sojourn at the Department of Information Technology (INTEC) at the Ghent University, Belgium, from january to june 2007. All-Optical Label Swapping (AOLS) forms a key technology towards the implementation of All-Optical Packet Switching nodes (AOPS) for the future optical Internet. The capital expenditures of the deployment of AOLS increases with the size of the label spaces (i.e. the number of used labels), since a special optical device is needed for each recognized label on every node. Label space sizes are affected by the wayin which demands are routed. For instance, while shortest-path routing leads to the usage of fewer labels but high link utilization, minimum interference routing leads to the opposite. This project studies and proposes All-Optical Label Stacking (AOLStack), which is an extension of the AOLS architecture. AOLStack aims at reducing label spaces while easing the compromise with link utilization. In this project, an Integer Lineal Program is proposed with the objective of analyzing the softening of the aforementioned trade-off due to AOLStack. Furthermore, a heuristic aiming at finding good solutions in polynomial-time is proposed as well. Simulation results show that AOLStack either a) reduces the label spaces with a low increase in the link utilization or, similarly, b) uses better the residual bandwidth to decrease the number of labels even more.

Orbit decidability and the conjugacy problem for some extensions of groups

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

The generic Hanna Neumann conjecture and post correspondence problem

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

Agglomeration and inequality across space: what can we learn from the European experience?

The purpose of this contribution is to draw a picture of the (uneven) distribution of economic activities across the states of the European Union (EU) and the consequences entailed by it. We will briefly summarize the most salient and recent contributions. Then, in the light of the economic geography theory, we will discuss the economic and social advantages and disadvantages associated with a core- periphery structure. In this sense, particular attention will be addressed to the EU financial system of Structural Funds and the effects they produced. Finally, we will formulate some suggestions, relying on the EU experience, that could be of interest to the current Brazilian regional policy.

Expansió accelerada de l’univers i teories de gravetat modificada a grans escales

Estudi realitzat a partir d’una estada al Physics Department de la New York University, United States, Estats Units, entre 2006 i 2008. Una de les observacions de més impacte en la cosmologia moderna ha estat la determinació empírica que l’Univers es troba actualment en una fase d’Expansió Accelerada (EA). Aquest fenòmen implica que o bé l’Univers està dominat per un nou sector de matèria/energia, o bé la Relativitat General deixa de tenir validesa a escales cosmològiques. La primera possibilitat comprèn els models d’Energia Fosca (EF), i el seu principal problema és que l’EF ha de tenir propietats tan especials que es fan difícils de justificar teòricament. La segona possibilitat requereix la construcció de teories consistents de Gravetat Modificada a Grans Distàncies (GMGD), que són una generalització dels models de gravetat massiva. L’interès fenomenològic per aquestes teories també va resorgir amb l’aparició dels primers exemples de models de GMGD, com ara el model de Dvali, Gabadadze i Porrati (DGP), que consisteix en un tipus de brana en una dimensió extra. Malauradament, però, aquest model no permet explicar de forma consistent l’EA de l’Univers. Un dels objectius d’aquest projecte ha estat establir la viabilitat interna i fenomenològica dels models de GMGD. Des del punt de vista fenomenològic, ens hem centrat en la questió més important a la pràctica: trobar signatures observacionals que permetin distingir els models de GMGD dels d’EF. A nivell més teòric, també hem investigat el significat de les inestabilitats del model DGP.L’altre gran objectiu que ens vam proposar va ser la construcció de noves teories de GMGD. En la segona part d’aquest projecte, hem elaborat i mostrat la consistència del model “DGP en Cascada”, que generalitza el model DGP a més dimensions extra, i representa el segon model consistent i invariant-Lorentz a l’espai pla conegut. L’existència d’altres models de GMGD més enllà de DGP és de gran interès atès que podria permetre obtenir l’EA de l’Univers de forma purament geomètrica.

The simultaneous conjugacy problem in groups of piecewise linear functions

Guba and Sapir asked, in their joint paper [8], if the simultaneous conjugacy problem was solvable in Diagram Groups or, at least, for Thompson's group F. We give an elementary proof for the solution of the latter question. This relies purely on the description of F as the group of piecewise linear orientation-preserving homeomorphisms of the unit. The techniques we develop allow us also to solve the ordinary conjugacy problem as well, and we can compute roots and centralizers. Moreover, these techniques can be generalized to solve the same questions in larger groups of piecewise-linear homeomorphisms.

Geometria integral i convexitat en espais de curvatura holomorfa constant

En aquest treball es tracten qüestions de la geometria integral clàssica a l'espai hiperbòlic i projectiu complex i a l'espai hermític estàndard, els anomenats espais de curvatura holomorfa constant. La geometria integral clàssica estudia, entre d'altres, l'expressió en termes geomètrics de la mesura de plans que tallen un domini convex fixat de l'espai euclidià. Aquesta expressió es dóna en termes de les integrals de curvatura mitja. Un dels resultats principals d'aquest treball expressa la mesura de plans complexos que tallen un domini fixat a l'espai hiperbòlic complex, en termes del que definim com volums intrínsecs hermítics, que generalitzen les integrals de curvatura mitja. Una altra de les preguntes que tracta la geometria integral clàssica és: donat un domini convex i l'espai de plans, com s'expressa la integral de la s-èssima integral de curvatura mitja del convex intersecció entre un pla i el convex fixat? A l'espai euclidià, a l'espai projectiu i hiperbòlic reals, aquesta integral correspon amb la s-èssima integral de curvatura mitja del convex inicial: se satisfà una propietat de reproductibitat, que no es té en els espais de curvatura holomorfa constant. En el treball donem l'expressió explícita de la integral de la curvatura mitja quan integrem sobre l'espai de plans complexos. L'expressem en termes de la integral de curvatura mitja del domini inicial i de la integral de la curvatura normal en una direcció especial: l'obtinguda en aplicar l'estructura complexa al vector normal. La motivació per estudiar els espais de curvatura holomorfa constant i, en particular, l'espai hiperbòlic complex, es troba en l'estudi del següent problema clàssic en geometria. Quin valor pren el quocient entre l'àrea i el perímetre per a successions de figures convexes del pla que creixen tendint a omplir-lo? Fins ara es coneixia el comportament d'aquest quocient en els espais de curvatura seccional negativa i que a l'espai hiperbòlic real les fites obtingudes són òptimes. Aquí provem que a l'espai hiperbòlic complex, les cotes generals no són òptimes i optimitzem la superior.

On a size-structured two-phase population model with infinite states-at-birth

In this work we introduce and analyze a linear size-structured population model with infinite states-at-birth. We model the dynamics of a population in which individuals have two distinct life-stages: an “active” phase when individuals grow, reproduce and die and a second “resting” phase when individuals only grow. Transition between these two phases depends on individuals’ size. First we show that the problem is governed by a positive quasicontractive semigroup on the biologically relevant state space. Then we investigate, in the framework of the spectral theory of linear operators, the asymptotic behavior of solutions of the model. We prove that the associated semigroup has, under biologically plausible assumptions, the property of asynchronous exponential growth.

Symmetry for a Dirichlet-Neumann problem arising in water waves

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

The non-linear Dirichlet problem in Hadamard manifolds

We prove existence theorems for the Dirichlet problem for hypersurfaces of constant special Lagrangian curvature in Hadamard manifolds. The first results are obtained using the continuity method and approximation and then refined using two iterations of the Perron method. The a-priori estimates used in the continuity method are valid in any ambient manifold.

Destruction of invariant curves in the restricted circular planar three body problem using comparison of action

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