On complexity of Ehrenfeucht–Fraïssé games

In this paper, we initiate the study of Ehrenfeucht–Fraïssé games for some standard finite structures. Examples of such standard structures are equivalence relations, trees, unary relation structures, Boolean algebras, and some of their natural expansions. The paper concerns the following question that we call the Ehrenfeucht–Fraïssé problem. Given nω as a parameter, and two relational structures and from one of the classes of structures mentioned above, how efficient is it to decide if Duplicator wins the n-round EF game ? We provide algorithms for solving the Ehrenfeucht–Fraïssé problem for the mentioned classes of structures. The running times of all the algorithms are bounded by constants. We obtain the values of these constants as functions of n.     

On Fraïssé’s conjecture for linear orders of finite Hausdorff rank

We prove that the maximal order type of the wqo of linear orders of finite Hausdorff rank under embeddability is φ₂(0), the first fixed point of the ε-function. We then show that Fraïssé’s conjecture restricted to linear orders of finite Hausdorff rank is provable in  +“φ₂(0) is well-ordered” and, over , implies  +“φ₂(0) is well-ordered”.     

On the Ehrenfeucht–Mycielski sequence

We introduce the inverted prefix tries (a variation of suffix tries) as a convenient formalism for stating and proving properties of the Ehrenfeucht–Mycielski sequence [A. Ehrenfeucht, J. Mycielski, A pseudorandom sequence—how random is it? American Mathematical Monthly 99 (1992) 373-375]. We also prove an upper bound on the position in the sequence by which all strings of a given length will have appeared; our bound is given by the Ackermann function, which, in light of experimental data, may be a gross over-estimate. Still, it is the best explicitly known upper bound at the moment. Finally, we show how to compute the next bit in the sequence in a constant number of operations.     

Twist–Rotation Transformations of Binary Trees and Arithmetic Expressions

The paper studies the computational complexity and efficient algorithms for the twist–rotation transformations of binary trees, which is equivalent to the transformation of arithmetic expressions over an associative and commutative binary operation. The main results are (1) a full binary tree with n labeled leaves can be transformed into any other in at most 3n log n + 2n twist and rotation operations, (2) deciding the twist–rotation distance between two binary trees is NP-complete, and (3) the twist–rotation transformation can be approximated with ratio 6 log n + 4 in polynomial time for full binary trees with n uniquely labeled leaves.     

Ahlfors-régularité des quasi-minima de Mumford–Shah

Let be an open set. We consider on Ω the competitors (U,K) for the reduced Mumford–Shah functional, that is to say the Mumford–Shah functional in which the -norm of U term is removed, where K is a closed subset of Ω and U is a function on ΩK with gradient in  . The main result of this paper is the following: there exists a constant c for which, whenever (U,K) is a quasi-minimizer for the reduced Mumford–Shah functional and B(x,r) is a ball centered on K and contained in Ω with bounded radius, the -measure of is bounded above by cr^N−1 and bounded below by c⁻¹r^N−1.     

Hermite–Padé approximation and simultaneous quadrature formulas

We study Hermite–Padé approximation of the so-called Nikishin systems of functions. In particular, the set of multi-indices for which normality is known to take place is considerably enlarged as well as the sequences of multi-indices for which convergence of the corresponding simultaneous rational approximants takes place. These results are applied to the study of the convergence properties of simultaneous quadrature rules of a given function with respect to different weights.     

Lévy–Ornstein–Uhlenbeck transition semigroup as second quantized operator

Let μ be an invariant measure for the transition semigroup (Pt) of the Markov family defined by the Ornstein-Uhlenbeck type equation

     

B-splines and Hermite–Padé approximants to the exponential function

This paper is the continuation of a work initiated in [P. Sablonnière, An algorithm for the computation of Hermite–Padé approximations to the exponential function: divided differences and Hermite–Padé forms. Numer. Algorithms 33 (2003) 443–452] about the computation of Hermite–Padé forms (HPF) and associated Hermite–Padé approximants (HPA) to the exponential function. We present an alternative algorithm for their computation, based on the representation of HPF in terms of integral remainders with B-splines as Peano kernels. Using the good properties of discrete B-splines, this algorithm gives rise to a great variety of representations of HPF of higher orders in terms of HPF of lower orders, and in particular of classical Padé forms. We give some examples illustrating this algorithm, in particular, another way of constructing quadratic HPF already described by different authors. Finally, we briefly study a family of cubic HPF.     

The uniform Korn–Poincaré inequality in thin domains

We study the Korn-Poincaré inequality:

‖u_‖W1,2(Sh)?Ch‖D(u)_‖L²(Sh),     

On the Divergence Phenomenon in Hermite–Fejér Interpolation

Generalizing results of L. Brutman and I. Gopengauz (1999, Constr. Approx.15, 611–617), we show that for any nonconstant entire function f and any interpolation scheme on [−1, 1], the associated Hermite–Fejér interpolating polynomials diverge on any infinite subset of \[−1, 1]. Moreover, it turns out that even for the locally uniform convergence on the open interval ]−1, 1[ it is necessary that the interpolation scheme converges to the arcsine distribution.     

Some properties of the Bézier–Kantorovich type operators

The aim of this paper is to present estimates for the rate of pointwise convergence of the Bézier–Kantorovich modification of the discrete Feller operators in some classes of measurable functions bounded on an interval I, in particular, for functions of bounded pth power variation on I. Our theorems generalize and extend the recent results of Zeng and Piriou (J. Approx. Theory 95(1998) 369; 104(2000) 330) for the kantorovichians of the Bernstein–Bézier operators in the class of functions of bounded variation in the Jordan sense on [0,1].     

A countable Fréchet–Urysohn space of uncountable character

We shall construct a countable Fréchet–Urysohn α₄ not α₃ space X such that all finite powers of X are Fréchet–Urysohn.     

NONTRIVIAL SOLUTIONS OF HARDY-HENON TYPE ELLIPTIC SYSTEMS

In this article,the authors investigate the existence problem for Hardy Hénon type strongly indefinite elliptic systems.Existence results are obtained for such systems with superlinear suberitical nonlinearities.     

Quadratic Hermite–Padé polynomials associated with the exponential function

The asymptotic behavior of quadratic Hermite–Padé polynomials associated with the exponential function is studied for n→∞. These polynomials are defined by the relation

(*)

p_n(z)+q_n(z)e^z+r_n(z)e^2z=O(z³ⁿ⁺²) as z→0,

where O(·) denotes Landau's symbol. In the investigation analytic expressions are proved for the asymptotics of the polynomials, for the asymptotics of the remainder term in (*), and also for the arcs on which the zeros of the polynomials and of the remainder term cluster if the independent variable z is rescaled in an appropriate way. The asymptotic expressions are defined with the help of an algebraic function of third degree and its associated Riemann surface. Among other possible applications, the results form the basis for the investigation of the convergence of quadratic Hermite–Padé approximants, which will be done in a follow-up paper.     

A Phragmén–Lindelöf alternative result for the Navier–Stokes equations for steady compressible viscous flow

In this paper, the authors consider the Navier–Stokes equations for steady compressible viscous flow in three-dimensional cylindrical domain. A differential inequality for appropriate energy associated with the solutions of the Navier–Stokes isentropic flow in semi-infinite pipe is derived, from which the authors show a Phragmén–Lindelöf alternative result, i.e. the solutions for steady compressible viscous N–S flow problem either grow or decay exponentially as the distance from the entry section tends to infinity. In the decay case, the authors indicate how to bound explicitly the total energy in terms of data.     

On the Domain of Divergence of Hermite–Fejér Interpolating Polynomials

Recently, the study of the behavior of the Hermite–Fejér interpolants in the complex plane was initiated by L. Brutman and I. Gopengauz (1999, Constr. Approx.15, 611–617). It was shown that, for a broad class of interpolatory matrices on [−1, 1], the sequence of polynomials induced by Hermite–Fejér interpolation to f(z)≡z diverges everywhere in the complex plane outside the interval of interpolation [−1, 1]. In this note we amplify this result and prove that the divergence phenomenon takes place without any restriction on the interpolatory matrices.