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.

Limit Cycles for a class of three dimensional polynomial differential systems

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

Polynomial and linearized normal forms for almost periodic differential systems

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

On the asymptotic expansion of the colored Jones polynomial for torus knots

In the asymptotic expansion of the hyperbolic specification of the colored Jones polynomial of torus knots, we identify different geometric contributions, in particular Chern-Simons invariant and Reidemeister torsion.

Algebraic properties of isochronous centers of polynomial quadratic-like Hamiltonian systems

Projecte de recerca elaborat a partir d’una estada a la School of Mathematics and Statistics de la University of Plymouth, United Kingdom, entre abril juliol del 2007.Aquesta investigació és encara oberta i la memòria que presento constitueix un informe de la recerca que estem duent a terme actualment. En aquesta nota estudiem els centres isòcrons dels sistemes Hamiltonians analítics, parant especial atenció en el cas polinomial. Ens centrem en els anomenats quadratic-like Hamiltonian systems. Diverses propietats dels centres isòcrons d'aquest tipus de sistemes van ser donades a [A. Cima, F. Mañosas and J. Villadelprat, Isochronicity for several classes of Hamiltonian systems, J. Di®erential Equations 157 (1999) 373{413]. Aquell article estava centrat principalment en el cas en que A; B i C fossin funcions analítiques. El nostre objectiu amb l'estudi que estem duent a terme és investigar el cas en el que aquestes funcions són polinomis. En aquesta nota formulem una conjectura concreta sobre les propietats algebraiques que venen forçades per la isocronia del centre i provem alguns resultats parcials.

Polynomial functors and trees

We explore the relationship between polynomial functors and trees. In the first part we characterise trees as certain polynomial functors and obtain a completely formal but at the same time conceptual and explicit construction of two categories of rooted trees, whose main properties we describe in terms of some factorisation systems. The second category is the category Ω of Moerdijk and Weiss. Although the constructions are motivated and explained in terms of polynomial functors, they all amount to elementary manipulations with finite sets. Included in Part 1 is also an explicit construction of the free monad on a polynomial endofunctor, given in terms of trees. In the second part we describe polynomial endofunctors and monads as structures built from trees, characterising the images of several nerve functors from polynomial endofunctors and monads into presheaves on categories of trees. Polynomial endofunctors and monads over a base are characterised by a sheaf condition on categories of decorated trees. In the absolute case, one further condition is needed, a projectivity condition, which serves also to characterise polynomial endofunctors and monads among (coloured) collections and operads.

Polynomial functors and polynomial monads

We study polynomial functors over locally cartesian closed categories. After setting up the basic theory, we show how polynomial functors assemble into a double category, in fact a framed bicategory. We show that the free monad on a polynomial endofunctor is polynomial. The relationship with operads and other related notions is explored.

An algorithm for semi-infinite polynomial optimization

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

Krein's strings whose spectral functions are of polynomial growth

In case Krein's strings with spectral functions of polynomial growth a necessary and su fficient condition for the Krein's correspondence to be continuous is given.

Bernstein's problem on weighted polynomial approximation

We formulate a necessary and sufficient condition for polynomials to be dense in a space of continuous functions on the real line, with respect to Bernstein's weighted uniform norm. Equivalently, for a positive finite measure [lletra "mu" minúscula de l'alfabet grec] on the real line we give a criterion for density of polynomials in Lp[lletra "mu" minúscula de l'alfabet grec entre parèntesis].

A polynomial algorithm for special case of the one-machine scheduling problem with time-lags

The standard one-machine scheduling problem consists in schedulinga set of jobs in one machine which can handle only one job at atime, minimizing the maximum lateness. Each job is available forprocessing at its release date, requires a known processing timeand after finishing the processing, it is delivery after a certaintime. There also can exists precedence constraints between pairsof jobs, requiring that the first jobs must be completed beforethe second job can start. An extension of this problem consistsin assigning a time interval between the processing of the jobsassociated with the precedence constrains, known by finish-starttime-lags. In presence of this constraints, the problem is NP-hardeven if preemption is allowed. In this work, we consider a specialcase of the one-machine preemption scheduling problem with time-lags, where the time-lags have a chain form, and propose apolynomial algorithm to solve it. The algorithm consist in apolynomial number of calls of the preemption version of the LongestTail Heuristic. One of the applicability of the method is to obtainlower bounds for NP-hard one-machine and job-shop schedulingproblems. We present some computational results of thisapplication, followed by some conclusions.

SAT Modulo Linear Arithmetic for Solving Polynomial

Polynomial constraint solving plays a prominent role in several areas of hardware and software analysis and verification, e.g., termination proving, program invariant generation and hybrid system verification, to name a few. In this paper we propose a new method for solving non-linear constraints based on encoding the problem into an SMT problem considering only linear arithmetic. Unlike other existing methods, our method focuses on proving satisfiability of the constraints rather than on proving unsatisfiability, which is more relevant in several applications as we illustrate with several examples. Nevertheless, we also present new techniques based on the analysis of unsatisfiable cores that allow one to efficiently prove unsatisfiability too for a broad class of problems. The power of our approach is demonstrated by means of extensive experiments comparing our prototype with state-of-the-art tools on benchmarks taken both from the academic and the industrial world.

Symmetric periodic orbits near heteroclinic loops at infinity for a class of polynomial vector fields

For polynomial vector fields in R3, in general, it is very difficult to detect the existence of an open set of periodic orbits in their phase portraits. Here, we characterize a class of polynomial vector fields of arbitrary even degree having an open set of periodic orbits. The main two tools for proving this result are, first, the existence in the phase portrait of a symmetry with respect to a plane and, second, the existence of two symmetric heteroclinic loops.

Integrability of a linear center perturbed by a fourth degree homogeneous polynomial

In this work we study the integrability of a two-dimensional autonomous system in the plane with linear part of center type and non-linear part given by homogeneous polynomials of fourth degree. We give sufficient conditions for integrability in polar coordinates. Finally we establish a conjecture about the independence of the two classes of parameters which appear in the system; if this conjecture is true the integrable cases found will be the only possible ones.

Integrability of a linear center perturbed by a fifth degree homogeneous polynomial

In this work we study the integrability of two-dimensional autonomous system in the plane with linear part of center type and non-linear part given by homogeneous polynomials of fifth degree. We give a simple characterisation for the integrable cases in polar coordinates. Finally we formulate a conjecture about the independence of the two classes of parameters which appear on the system; if this conjecture is true the integrable cases found will be the only possible ones.