Pseudo-représentations

Sans résumé

---

     

Congruences,equational theories and lattice representations

We survey results concerning the representations of lattices as lattices of congruences and as lattices of equational theories. Recent results and open problems will be mentioned.To László Fuchs on the occasion of his 70th birthday     

Large-time behavior of perturbed diffusion markov processes with applications to the second eigenvalue problem for fokker-planck operators and simulated annealing

We study the large-time behavior and rate of convergence to the invariant measures of the processes dX (t)=b(X) (t)) dt + (X (t)) dB(t). A crucial constant appears naturally in our study. Heuristically, when the time is of the order exp( – )/² , the transition density has a good lower bound and when the process has run for about exp( – )/², it is very close to the invariant measure. LetL =(²/2) – U · be a second-order differential operator on ^d. Under suitable conditions,L ^z has the discrete spectrum

On the geometries of the rational unfoldings of X k

With a view to applications to self-regulating dynamical processes in biology, we determine the geometric structure of what we call isotangent curves, i.e. curves parametrized by the slopes of their points. They come up naturally as bifurcation curves of rational unfoldings of X ^k, and we classify them according to degree and number of cusps. They, as well as their isotangent involute curves, turn up in simulations of these processes.     

The Binet-Pexider functional equation for rectangular matrices

IfK is a field of characteristic 0 then the following is shown. Iff, g, h: M _n (K) K are non-constant solutions of the Binet—Pexider functional equation

Parallel and superfast algorithms for Hankel systems of equations

Summary Utilizing kernel structure properties a unified construction of Hankel matrix inversion algorithms is presented. Three types of algorithms are obtained: 1)O(n ²) complexity Levinson type, 2)O (n) parallel complexity Schur-type, and 3)O(n log² n) complexity asymptotically fast ones. All algorithms work without additional assumption (like strong nonsingularity).     

The Weierstrass mean

Theorem.Let the sequences {e _i ⁽ⁿ⁾ },i=1, 2, 3,n=0, 1, 2, ...be defined by where the e ⁽⁰⁾ s satisfy and where all square roots are taken positive. Then where the convergence is quadratic and monotone and where The discussions of convergence are entirely elementary. However, although the determination of the limits can be made in an elementary way, an acquaintance with elliptic objects is desirable for real understanding.     

Heat “polynomials” for a singular differential operator on (0, ∞)

We generalize the theory of the heat polynomials introduced by P. V. Rosenbloom and D. V. Widder for a more general class of singular differential operator on (0, ). The heat polynomials associated with the Bessel operator and studied by D. T. Haimo appear as a particular case in this paper. In the special cases of second derivative and Bessel operators the heat polynomials are in fact polynomials inx andt, however, this property does not hold in general.Communicated by Tom. H. Koornwinder.     

Query complexity,or why is it difficult to separateNP A ∩coNP A fromP A by random oraclesA?

By thequery-time complexity of a relativized algorithm we mean the total length of oracle queries made; thequery-space complexity is the maximum length of the queries made. With respect to these cost measures one can define polynomially time- or space-bounded deterministic, nondeterministic, alternating, etc. Turing machines and the corresponding complexity classes. It turns out that all known relativized separation results operate essentially with this cost measure. Therefore, if certain classes do not separate in the query complexity model, this can be taken as an indication that their relativized separation in the classical cost model will require entirely new principles.A notable unresolved question in relativized complexity theory is the separation of NP^A co NP^A fromP ^A under random oraclesA. We conjecture that the analogues of these classes actually coincide in the query complexity model, thus indicating an answer to the question in the title. As a first step in the direction of establishing the conjecture, we prove the following result, where polynomial bounds refer to query complexity.If two polynomially query-time-bounded nondeterministic oracle Turing machines accept precisely complementary (oracle dependent) languages L^A and {0, 1}^*L^A under every oracle A then there exists a deterministic polynomially query-time-bounded oracle Turing machine that accept L^A. The proof involves a sort of greedy strategy to selecting deterministically, from the large set of prospective queries of the two nondeterministic machines, a small subset that suffices to perform an accepting computation in one of the nondeterministic machines. We describe additional algorithmic strategies that may resolve the same problem when the condition holds for a (1–) fraction of the oracles A, a step that would bring us to a non-uniform version of the conjecture. Thereby we reduce the question to a combinatorial problem on certain pairs of sets of partial functions on finite sets.