Mean-payoff games and propositional proofs

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

Weak systems of Gandy, Jensen and Devlin

In Part I, we formulate and examine some systems that have arisen in the study of the constructible hierarchy; we find numerous transitive models for them, among which are supertransitive models containing all ordinals that show that Devlin's system BS lies strictly between Gandy's systems PZ and BST'; and we use our models to show that BS fails to handle even the simplest rudimentary functions, and is thus inadequate for the use intended for it in Devlin's treatise. In Part II we propose and study an enhancement of the underlying logic of these systems, build further models to show where the previous hierarchy of systems is preserved by our enhancement; and consider three systems that might serve for Devlin's purposes: one the enhancement of a version of BS, one a formulation of Gandy-Jensen set theory, and the third a subsystem common to those two. In Part III we give new proofs of results of Boffa by constructing three models in which, respectively, TCo, AxPair and AxSing fail; we give some sufficient conditions for a set not to belong to the rudimentary closure of another set, and thus answer a question of McAloon; and we comment on Gandy's numerals and correct and sharpen other of his observations.

Payoff-dependent balancedness and cores (revised version)

We prove the non-emptiness of the core of an NTU game satisfying a condition of payoff-dependent balancedness, based on transfer rate mappings. We also define a new equilibrium condition on transfer rates and we prove the existence of core payoff vectors satisfying this condition. The additional requirement of transfer rate equilibrium refines the core concept and allows the selection of specific core payoff vectors. Lastly, the class of parametrized cooperative games is introduced. This new setting and its associated equilibrium-core solution extend the usual cooperative game framework and core solution to situations depending on an exogenous environment. A non-emptiness result for the equilibrium-core is also provided in the context of a parametrized cooperative game. Our proofs borrow mathematical tools and geometric constructions from general equilibrium theory with non convexities. Applications to extant results taken from game theory and economic theory are given.

Subgroups of small index in Aut(Fn) and Kazhdan's property (T)

We give a series of interesting subgroups of finite index in Aut(Fn). One of them has index 42 in Aut(F3) and infinite abelianization. This implies that Aut(F3) does not have Kazhdan’s property (T) (see [3] and [6] for another proofs). We proved also that every subgroup of finite index in Aut(Fn), n &= 3, which contains the subgroup of IA-automorphisms, has a finite abelianization.

Coupling and monotonicity of queueing processes

The main purpose of this work is to give a survey of main monotonicity properties of queueing processes based on the coupling method. The literature on this topic is quite extensive, and we do not consider all aspects of this topic. Our more concrete goal is to select the most interesting basic monotonicity results and give simple and elegant proofs. Also we give a few new (or revised) proofs of a few important monotonicity properties for the queue-size and workload processes both in single-server and multi- server systems. The paper is organized as follows. In Section 1, the basic notions and results on coupling method are given. Section 2 contains known coupling results for renewal processes with focus on construction of synchronized renewal instants for a superposition of independent renewal processes. In Section 3, we present basic monotonicity results for the queue-size and workload processes. We consider both discrete-and continuous-time queueing systems with single and multi servers. Less known results on monotonicity of queueing processes with dependent service times and interarrival times are also presented. Section 4 is devoted to monotonicity of general Jackson-type queueing networks with Markovian routing. This section is based on the notable paper [17]. Finally, Section 5 contains elements of stability analysis of regenerative queues and networks, where coupling and monotonicity results play a crucial role to establish minimal suficient stability conditions. Besides, we present some new monotonicity results for tandem networks.

Disseny i desenvolupament de videojocs

Estudi i implementació d’una plataforma de prototipatge de videojocs mitjançant la qual es pot crear un videojoc elemental, descartant aspectes decoratius o accessoris. Aquesta eina pretén millorar l’etapa de disseny d’un videojoc avançant el moment en que aquest es podrà jugar. Això permetrà prendre decisions importants en base a proves i experiències mesurables. S’ha implementat un sistema programable en llenguatge de script que estalvia a l’usuari treballar en els aspectes tecnològics i li permet centrar-se en crear la mecànica del joc que vol ser provat.

Amor i literatura: dos conceptes per a la creació d'una novel·la

Treball de recerca realitzat per una alumna d'ensenyament secundari i guardonat amb un Premi CIRIT per fomentar l'esperit cientí­fic del Jovent l'any 2009. L'amor, l'etern tema en el món literari és el protagonista de la temàtica en què se centra el projecte però, des de les primeres mostres literàries fins l'actualitat són infinites les creacions aparegudes. El treball s'ha centrat en algunes que són una digna representació de l'amor literari en cada època i en diverses parts de la literatura universal. Fins aquí un plantejament que no s'alunya de cap model realitzat dins de la temàtica de la literatura comparada. Però per solucionar la manca d'un fil conductor es va crear una novel·la que és la que guia aquest treball. Així es mostra el que una persona pot extreure llegint diverses obres d'amor literari, i no només sobre teories generals, sinó també d'opinions i pròpies emocions que provoca l'experiència de lectura. De la mà d en Marco, un jove veronès, i la seva vella amiga, la bibliotecària Sophie, es guia al lector a través d'un viatge que sorgeix de les primeres mostres d'amor escrit i arriba fins als nostres dies.

Index theory for basic Dirac operators on Riemannian foliations

In this paper we prove a formula for the analytic index of a basic Dirac-type operator on a Riemannian foliation, solving a problem that has been open for many years. We also consider more general indices given by twisting the basic Dirac operator by a representation of the orthogonal group. The formula is a sum of integrals over blowups of the strata of the foliation and also involves eta invariants of associated elliptic operators. As a special case, a Gauss-Bonnet formula for the basic Euler characteristic is obtained using two independent proofs.

A linear optimization technique for graph pebbling

Graph pebbling is a network model for studying whether or not a given supply of discrete pebbles can satisfy a given demand via pebbling moves. A pebbling move across an edge of a graph takes two pebbles from one endpoint and places one pebble at the other endpoint; the other pebble is lost in transit as a toll. It has been shown that deciding whether a supply can meet a demand on a graph is NP-complete. The pebbling number of a graph is the smallest t such that every supply of t pebbles can satisfy every demand of one pebble. Deciding if the pebbling number is at most k is NP 2 -complete. In this paper we develop a tool, called theWeight Function Lemma, for computing upper bounds and sometimes exact values for pebbling numbers with the assistance of linear optimization. With this tool we are able to calculate the pebbling numbers of much larger graphs than in previous algorithms, and much more quickly as well. We also obtain results for many families of graphs, in many cases by hand, with much simpler and remarkably shorter proofs than given in previously existing arguments (certificates typically of size at most the number of vertices times the maximum degree), especially for highly symmetric graphs. Here we apply theWeight Function Lemma to several specific graphs, including the Petersen, Lemke, 4th weak Bruhat, Lemke squared, and two random graphs, as well as to a number of infinite families of graphs, such as trees, cycles, graph powers of cycles, cubes, and some generalized Petersen and Coxeter graphs. This partly answers a question of Pachter, et al., by computing the pebbling exponent of cycles to within an asymptotically small range. It is conceivable that this method yields an approximation algorithm for graph pebbling.

Sharpened lower bounds for cut elimination

We present sharpened lower bounds on the size of cut free proofs for first-order logic. Prior lower bounds for eliminating cuts from a proof established superexponential lower bounds as a stack of exponentials, with the height of the stack proportional to the maximum depth d of the formulas in the original proof. Our new lower bounds remove the constant of proportionality, giving an exponential stack of height equal to d − O(1). The proof method is based on more efficiently expressing the Gentzen-Solovay cut formulas as low depth formulas.

Analitzador gràfic de xarxa en entorn GNU

Treball de fi de carrera d'enginyeria tècnica en informàtica de sistemes. El treball s'estructura en introducció, anàlisi, implementació, manual d'instal·lació, joc de proves... del treball. Aquest Treball Final de Carrera s'inclou dins de l'àrea de Xarxes deComputadors. Consisteix en la realització d'una aplicació gràfica en entornGNU que faci un anàlisi del tràfic d'una xarxa informàtica; això es coneix ambel nom de Sniffer.

Some conceptual difficulties regarding "net" multipliers

Multipliers are routinely used for impact evaluation of private projects and public policies at the national and subnational levels. Oosterhaven and Stelder (2002) correctly pointed out the misuse of standard 'gross' multipliers and proposed the concept of 'net' multiplier as a solution to this bad practice. We prove their proposal is not well founded. We do so by showing that supporting theorems are faulty in enunciation and demonstration. The proofs are flawed due to an analytical error but the theorems themselves cannot be salvaged as generic, non-curiosum counterexamples demonstrate. We also provide a general analytical framework for multipliers and, using it, we show that standard 'gross' multipliers are all that is needed within the interindustry model since they follow the causal logic of the economic model, are well defined and independent of exogenous shocks, and are interpretable as predictors for change.

Fermat's treatise on quadrature: A new reading

The Treatise on Quadrature of Fermat (c. 1659), besides containing the first known proof of the computation of the area under a higher parabola, R x+m/n dx, or under a higher hyperbola, R x-m/n dx with the appropriate limits of integration in each case , has a second part which was not understood by Fermat s contemporaries. This second part of the Treatise is obscure and difficult to read and even the great Huygens described it as'published with many mistakes and it is so obscure (with proofs redolent of error) that I have been unable to make any sense of it'. Far from the confusion that Huygens attributes to it, in this paper we try to prove that Fermat, in writing the Treatise, had a very clear goal in mind and he managed to attain it by means of a simple and original method. Fermat reduced the quadrature of a great number of algebraic curves to the quadrature of known curves: the higher parabolas and hyperbolas of the first part of the paper. Others, he reduced to the quadrature of the circle. We shall see how the clever use of two procedures, quite novel at the time: the change of variables and a particular case of the formulaof integration by parts, provide Fermat with the necessary tools to square very easily curves as well-known as the folium of Descartes, the cissoid of Diocles or the witch of Agnesi.

Vortices and extreme black holes: The question of flux expulsion

It has been claimed that extreme black holes exhibit a phenomenon of flux expulsion for Abelian Higgs vortices, irrespective of the relative width of the vortex to the black hole. Recent work by two of the authors showed a subtlety in the treatment of the event horizon, which cast doubt on this claim. We analyze in detail the vortexextreme black hole system, showing that, while flux expulsion can occur, it does not do so in all cases. We give analytic proofs for both expulsion and penetration of flux, in each case deriving a bound for that behavior. We also present extensive numerical work backing up, and refining, these claims, and showing in detail how a vortex can end on a black hole in all situations. We also calculate the back reaction of the vortex on the geometry, and comment on the more general vortexblack hole system.

Self-organized criticality induced by diversity

We have studied the collective behavior of a population of integrate-and-fire oscillators. We show that diversity, introduced in terms of a random distribution of natural periods, is the mechanism that permits one to observe self-organized criticality (SOC) in the long time regime. As diversity increases the system undergoes several transitions from a supercritical regime to a subcritical one, crossing the SOC region. Although there are resemblances with percolation, we give proofs that criticality takes place for a wide range of values of the control parameter instead of a single value.