On Simple Polygonalizations with Optimal Area

We discuss the problem of finding a simple polygonalization for a given set of vertices P that has optimal area. We show that these problems are very closely related to problems of optimizing the number of points from a set Q in a simple polygon with vertex set P and prove that it is NP-complete to find a minimum weight polygon or a maximum weight polygon for a given vertex set, resulting in a proof of NP-completeness for the corresponding area optimization problems. This answers a generalization of a question stated by Suri in 1989. Finally, we turn to higher dimensions, where we prove that, for 1 k d , 2 d , it is NP-hard to determine the smallest possible total volume of the k -dimensional faces of a d -dimensional simple nondegenerate polyhedron with a given vertex set, answering a generalization of a question stated by O'Rourke in 1980. Received June 26, 1997, and in revised form February 13, 1999, and May 19, 1999.     

The computational complexity of basic decision problems in 3-dimensional topology

We study the computational complexity of basic decision problems of 3-dimensional topology, such as to determine whether a triangulated 3-manifold is irreducible, prime, ∂-irreducible, or homeomorphic to a given 3-manifold M. For example, we prove that the problem to recognize whether a triangulated 3-manifold is homeomorphic to a 3-sphere, or to a 2-sphere bundle over a circle, or to a real projective 3-space, or to a handlebody of genus g, is decidable in nondeterministic polynomial time (NP) of size of the triangulation. We also show that the problem to determine whether a triangulated orientable 3-manifold is irreducible (or prime) is in PSPACE and whether it is ∂-irreducible is in coNP. The proofs improve and extend arguments of prior author’s article on the recognition problem for the 3-sphere.      

Quantum chaos and fractals with atoms in cavities

We study the coupled translational, electronic, and field dynamics of the combined system “a two-level atom + a single-mode quantized field + a standing-wave ideal cavity”. In the semiclassical approximation with a point-like atom, interacting with the classical field, the dynamics is described by the Heisenberg equations for the atomic and field expectation values which are known to produce semiclassical chaos under appropriate conditions. We derive Hamilton–Schrödinger equations for probability amplitudes and averaged position and momentum of a point-like atom interacting with the quantized field in a standing-wave cavity. They constitute, in general, an infinite-dimensional set of equations with an infinite number of integrals of motion which may be reduced to a dynamical system with four degrees of freedom if the quantized field is supposed to be initially prepared in a Fock state. This system is found to produce semiquantum chaos with positive values of the maximal Lyapunov exponent. At exact resonance, the semiquantum dynamics is regular. At large values of detuning |δ|1, the Rabi atomic oscillations are usually shallow, and the dynamics is found to be almost regular. The Doppler–Rabi resonance, deep Rabi oscillations that may occur at any large value of |δ| to be equal to |αp₀|, is found numerically and described analytically (with α to be the normalized recoil frequency and p₀ the initial atomic momentum). Two gedanken experiments are proposed to detect manifestations of semiquantum chaos in real experiments. It is shown that in the chaotic regime values of the population inversion z_out, measured with atoms after transversing a cavity, are so sensitive to small changes in the initial inversion z_in that the probability of detecting any value of z_out in the admissible interval [−1,1] becomes almost unity in a short time. Chaotic wandering of a two-level atom in a quantized Fock field is shown to be fractal. Fractal-like structures, typical with chaotic scattering, are numerically found in the dependence of the time of exit of atoms from the cavity on their initial momenta.     

On Rockafellar’s theorem using proximal point algorithm involving -maximal monotonicity framework

On the basis of the general framework of H-maximal monotonicity (also referred to as H-monotonicity in the literature), a generalization to Rockafellar’s theorem in the context of solving a general inclusion problem involving a set-valued maximal monotone operator using the proximal point algorithm in a Hilbert space setting is explored. As a matter of fact, this class of inclusion problems reduces to a class of variational inequalities as well as to a class of complementarity problems. This proximal point algorithm turns out to be of interest in the sense that it plays a significant role in certain computational methods of multipliers in nonlinear programming. The notion of H-maximal monotonicity generalizes the general theory of set-valued maximal monotone mappings to a new level. Furthermore, some results on general firm nonexpansiveness and resolvent mapping corresponding to H-monotonicity are also given.     

Modules in Which Every Fully Invariant Submodule is Essential in a Direct Summand

A module M is called extending if every submodule of M is essential in a direct summand. We call a module FI-extending if every fully invariant submodule is essential in a direct summand. Initially we develop basic properties in the general module setting. For example, in contrast to extending modules, a direct sum of FI-extending modules is FI-extending. Later we largely focus on the specific case when a ring is FI-extending (considered as a module over itself). Again, unlike the extending property, the FI-extending property is shown to carry over to matrix rings. Several results on ring direct decompositions of FI-extending rings are obtained, including a proper generalization of a result of C. Faith on the splitting-off of the maximal regular ideal in a continuous ring.     

Weak Convergence of a Sequence of Semimartingales to a Diffusion with Discontinuous Drift and Diffusion Coefficients

This paper presents a set of sufficient conditions for a sequence of semimartingales to converge weakly to a solution of a stochastic differential equation (SDE) with discontinuous drift and diffusion coefficients. This result is closely related to a well-known weak-convergence theorem due to Liptser and Shiryayev (see [27]) which proves the weak convergence to a solution of a SDE with continuous drift and diffusion coefficients in the Skorokhod–Lindvall J ₁-topology.The goal of this paper is to obtain a stronger result in order to solve outstanding problems in the area of large-scale queueing networks – in which the weak convergence of normalized queueing length is a solution of a SDE with discontinuous coefficients. To do this we need to make the stronger assumptions: (1) replacing the convergence in probability of the triplets of a sequence of semimartingales in the original Liptser and Shiryayev's theorem by stronger convergence in L ₂, (2) assuming the diffusion coefficient is coercive, and (3) assuming the discontinuity sets of the coefficients of the limit diffusion processs are of Lebesgue measure zero.     

A vertex incremental approach for maintaining chordality

For a chordal graph G=(V,E), we study the problem of whether a new vertex u∉V and a given set of edges between u and vertices in V can be added to G so that the resulting graph remains chordal. We show how to resolve this efficiently, and at the same time, if the answer is no, specify a maximal subset of the proposed edges that can be added along with u, or conversely, a minimal set of extra edges that can be added in addition to the given set, so that the resulting graph is chordal. In order to do this, we give a new characterization of chordal graphs and, for each potential new edge uv, a characterization of the set of edges incident to u that also must be added to G along with uv. We propose a data structure that can compute and add each such set in O(n) time. Based on these results, we present an algorithm that computes both a minimal triangulation and a maximal chordal subgraph of an arbitrary input graph in O(nm) time, using a totally new vertex incremental approach. In contrast to previous algorithms, our process is on-line in that each new vertex is added without reconsidering any choice made at previous steps, and without requiring any knowledge of the vertices that might be added subsequently.     

Uniqueness cases in odd-type groups of finite Morley rank

There is a longstanding conjecture, due to Gregory Cherlin andBoris Zilber, that all simple groups of finite Morley rank aresimple algebraic groups. One of the major theorems in the areais Borovik's trichotomy theorem. The ‘trichotomy’here is a case division of the generic minimal counterexampleswithin odd type, that is, groups with a large and divisibleSylow° 2-subgroup. The so-called ‘uniqueness case’in the trichotomy theorem is the existence of a proper 2-generatedcore. It is our aim to drive the presence of a proper 2-generatedcore to a contradiction, and hence bind the complexity of theSylow° 2-subgroup of a minimal counterexample to the Cherlin–Zilberconjecture. This paper shows that the group in question is aminimal connected simple group and has a strongly embedded subgroup,a far stronger uniqueness case. As a corollary, a tame counterexampleto the Cherlin–Zilber conjecture has Prüfer rankat most two.     

The second twisted Betti number and the convergence of collapsing Riemannian manifolds

Let M _i X denote a sequence of n-manifolds converging to a compact metric space, X, in the Gromov-Hausdorff topology such that the sectional curvature is bounded in absolute value and dim(X)<n. We prove the following stability result: If the fundamental groups of M _i are torsion groups of uniformly bounded exponents and the second twisted Betti numbers of M _i vanish, then there is a manifold, M, and a sequence of diffeomorphisms from M to a subsequence of {M _i } such that the distance functions of the pullback metrics converge to a pseudo-metric in C ⁰-norm. Furthermore, M admits a foliation with leaves diffeomorphic to flat manifolds (not necessarily compact) such that a vector is tangent to a leaf if and only if its norm converges to zero with respect to the pullback metrics. These results lead to a few interesting applications. Oblatum 17-I-2002 & 27-II-2002?Published online: 29 April 2002     

Champs affines

The purpose of this work is to introduce a notion of affine stacks, which is a homotopy version of the notion of affine schemes, and to give several applications in the context of algebraic topology and algebraic geometry. As a first application we show how affine stacks can be used in order to give a new point of view (and new proofs) on rational and p-adic homotopy theory. This gives a first solution to A. Grothendieck’s schematization problem described in [18]. We also use affine stacks in order to introduce a notion of schematic homotopy types. We show that schematic homotopy types give a second solution to the schematization problem, which also allows us to go beyond rational and p-adic homotopy theory for spaces with arbitrary fundamental groups. The notion of schematic homotopy types is also used in order to construct various homotopy types of algebraic varieties corresponding to various co-homology theories (Betti, de Rham, l-adic, ...), extending the well known constructions of the various fundamental groups. Finally, just as algebraic stacks are obtained by gluing affine schemes we define $$ \infty $$-geometric stacks as a certain gluing of affine stacks. Examples of $$ \infty $$-geometric stacks in the context of algebraic topology (moduli spaces of dga structures up to quasi-isomorphisms) and Hodge theory (non-abelian periods) are given.     

Application of Hankel transforms to boundary value problems of water flow due to a circular source

With the aid of Hankel transform technique, we obtain close-form solutions for discontinuous boundary-condition problems of water flow due to a circular source, which located on the upper surface of a confined aquifer. Owing to difficult evaluations of the original solutions that are in a form of an infinite range integral with a singular point and Bessel functions in integrands, we adopt two numerical algorisms to transform the original solutions as a series form for convenient practical applications. We apply the solutions in series form to numerical examples to analyze the characteristics of the flow in the confined aquifers subjected to pumping or recharge. By numerical examples, it indicates that: the drawdown will reduce with the increase of the layer thickness and the distance from the center of a circular source when pumping in a region with a finite thickness and a finite width; two algorisms for closed-form solutions of an infinite range integral have almost the same results, but the second algorism is superior for a faster convergence; in a semi-infinite confined aquifer, the drawdown due to a constant pumping rate Q and uplift due to recharge by a given hydraulic head s₀ will both decrease with the increase of K_r/K_v; however, the radius r₀ of the circular source has a reverse influence on the drawdown and the uplift, i.e., the drawdown decrease with the increase of r₀, while the uplift increase with r₀.     

On Mixed Error Estimates for Elliptic Obstacle Problems

We establish in this paper sharp error estimates of residual type for finite element approximation to elliptic obstacle problems. The estimates are of mixed nature, which are neither of a pure a priori form nor of a pure a posteriori form but instead they are combined by an a priori part and an a posteriori part. The key ingredient in our derivation for the mixed error estimates is the use of a new interpolator which enables us to eliminate inactive data from the error estimators. One application of our mixed error estimates is to construct a posteriori error indicators reliable and efficient up to higher order terms, and these indicators are useful in mesh-refinements and adaptive grid generations. In particular, by approximating the a priori part with some a posteriori quantities we can successfully track the free boundary for elliptic obstacle problems.     

The rational canonical form via the splitting field

It is clear that a given rational canonical form can be further resolved to a Jordan canonical form with entries from the splitting field of its minimal polynomial. Conversely, with an a priori knowledge of the existence and uniqueness of the rational canonical form of a matrix with entries from a general field, one can modify its Jordan canonical form in the splitting field of its minimal polynomial to construct its rational canonical form in the original field. No author has tried this converse with the a priori existence–uniqueness condition removed. It is feared that “in many occasions when, after a result has been established for a matrix with entries in a given field, considered as a matrix with entries in a finite extension of that field, we cannot go back from the extension field to get the desired information in the original field” [I.N. Herstein, Topics in Algebra, Ginn and Company, Waltham, MA, 1964 (pp. 262–263)]. The present paper removes this a priori condition and uses a “symmetrization” to “integrate” back the Jordan canonical form of a matrix to its rational canonical form in the original field.     

On surfaces and their contours

We prove two theorems concerning the global behaviour of a smooth compact surfaceS, without boundary, embedded in a real projective space or mapped to a plane. Our starting point is an analysis of the orientability properties of the normal bundle of a singular projective curve. Then we see how an excellent projection fromS to the Euclidean plane gives rise to integral relations linking the singularities of the apparent contour. Finally, given an embedding ofS in RPⁿ, we look at the discriminant Δ^* of a net of hyperplanes that intersectsS in a generic way, obtaining a characterization of Δ^* in terms of mod.2 cohomology invariants.     

Stochastic approximation of Banach-valued random variables with smooth distributions

A random variablef taking values in a Banach spaceE is estimated from another Banach-valued variableg. The best (with respect to theL _p-metrix) estimator is proved to exist in the case of Bochnerp-integrable variables. For a Hilbert spaceE andp=2, the best estimator is expressed in terms of the conditional expectation and, in the case of jointly Gaussian variables, in terms of the orthoprojection on a certain subspace ofE. More explicit expressions in terms of surface measures are given for the case in which the underlying probability space is a Hilbert space with a smooth probability measure. The results are applied to the Wiener process to improve earlier estimates given by K. Ritter [4]. Translated fromMatematicheskie Zametki, Vol. 58, No. 3, pp. 425–444, September, 1995. The author is grateful to B. S. Kashin for posing the problem and helping to write the article, and to the reviewer for a number of useful remarks.     

Applied linguistics: Optimization of semantic relations by data aggregation techniques

After a short methodological presentation of similarity aggregation in automatic classification, we will present an application to computational linguistics. We will try to explain, from an existing dictionary of synonyms, how we have

• (a) defined what was, in our opinion, the meaning of the synonymous relation we wanted to reveal in a new optimized dictionary,
• (b) transformed the existing dictionary into a sequence of matrices of synonymy,
• (c) checked with an adapted algorithm (similarity aggregation technique) if the links appearing in the existing dictionary corresponded to our synonymy definition,
• (d) tried to improve the synonymous relation,

in order to propose more accurate data facilitating the management of a new dictionary and providing a classification of synonyms according to a semic separate valuation.     

The Interplay Between Fairness and Randomness in a Spatial Computer Game

This article describes how children use an expressive microworld to articulate ideas about how to make a game seem fair with the use of randomness. Our aim in this study is to disentangle different flavours of fairness and to find out how children used each flavour to make sense of potentially complex behaviour. In order to achieve this, a spatial computer game was designed to enable children to examine the consequences of their attempts to make the game fair. The study investigates how 23 children, aged between 5.5 and 8 years, engaged in constructing a crucial part of a mechanism for a fair spatial lottery machine (microworld). In particular, the children tried to construct a fair game given a situation in which the key elements happened randomly. The children could select objects, determine their properties, and arrange their spatial layout in the machine. The study is based on task-based interviewing of children who were interacting with the computer game. The study shows that children have various cognitive resources for constructing a random fair environment. The spatial arrangement, the visualisation and the manipulations in the lottery machine allow us gain a view into the children’s thinking of the two central concepts, fairness and randomness. The paper reports on two main strategies by which the children attempted to achieve a balance in the lottery machine. One involves arranging the balls symmetrically and the other randomly. We characterize the nature of the thinking in these two strategies: the first we see as deterministic and the latter as stochastic, exploiting the random collisions of the ball. In this article we trace how the children’s thinking moved between these two perspectives.

有限维逼近无限维总极值的水平值估计方法

变分计算、最优控制、微分对策等常常要求考虑无限维空间中的总极值问题,但实际计算中只能得出有限维空间中的解.本文用有限维逼近无限维的方法来讨论函数空间中的总体最优化问题.用水平值估计和变侧度方法来求得有限维逼近总体最优化问题.对于有约束问题,用不连续精确罚函数法将其转化为无约束问题求解.     

Nearest-neighbour modelling of reciprocal chains

This paper focuses on the class of finite-state, discrete-index, reciprocal processes (reciprocal chains). Such a class of processes seems to be a suitable setup in many applications and, in particular, it appears well-suited for image-processing. While addressing this issue, the aim is 2-fold: theoretic and practical. As to the theoretic purpose, some new results are provided: first, a general stochastic realization result is provided for reciprocal chains endowed with a known, arbitrary, distribution. Such a model has the form of a fixed-degree, nearest-neighbour polynomial model. Next, the polynomial model is shown to be exactly linearizable, which means it is equivalent to a nearest-neighbour linear model in a different set of variables. The latter model turns out to be formally identical to the Levi–Frezza–Krener linear model of a Gaussian reciprocal process, although actually non-linear with respect to the chain's values. As far as the practical purpose is concerned, in order to yield an example of application an estimation issue is addressed: a suboptimal (polynomial-optimal) solution is derived for the smoothing problem of a reciprocal chain partially observed under non-Gaussian noise. To this purpose, two kinds of boundary conditions (Dirichlet and Cyclic), specifying the reciprocal chain on a finite interval, are considered, and in both cases the model is shown to be well-posed, in a ‘wide-sense’. Under this view, some well-known representation results about Gaussian reciprocal processes extend, in a sense, to a ‘non-Gaussian’ case.