### Article

## Minimum—weight perfect matching for nonintrinsic distances on the line

Given a closed interval $I=[a,b]$ and a metric space $(M,d)$, we introduce a

nondecreasing sequence $\{\nu_n\}$ of pseudometrics on $M^I$ (the set of all

functions from $I$ into $M$), called the {\it joint modulus of variation}. We show that

if two sequences of functions $\{f_j\}$ and $\{g_j\}$ from $M^I$ are such that

$\{f_j\}$ is pointwise relatively compact on $I$, $\{g_j\}$ is pointwise convergent on $I$,

and $\limsup_{j\to\infty}\nu_n(f_j,g_j)=o(n)$ as $n\to\infty$, then $\{f_j\}$ admits

a pointwise convergent subsequence whose limit on $I$ is a conditionally regulated function.

The notion of a modular is introduced as follows. A (metric) *modular* on a set *X* is a function *w*:(0,*∞*)×*X*×*X*→[0,*∞*] satisfying, for all *x*,*y*,*z*∈*X*, the following three properties: *x*=*y* if and only if *w*(*λ*,*x*,*y*)=0 for all *λ*>0; *w*(*λ*,*x*,*y*)=*w*(*λ*,*y*,*x*) for all *λ*>0; *w*(*λ*+*μ*,*x*,*y*)≤*w*(*λ*,*x*,*z*)+*w*(*μ*,*y*,*z*) for all *λ*,*μ*>0. We show that, given *x*0∈*X*, the set *X**w*={*x*∈*X*:lim*λ*→*∞**w*(*λ*,*x*,*x*0)=0} is a metric space with metric , called a *modular space*. The modular *w* is said to be *convex* if (*λ*,*x*,*y*)↦*λ**w*(*λ*,*x*,*y*) is also a modular on *X*. In this case *X**w* coincides with the set of all *x*∈*X* such that *w*(*λ*,*x*,*x*0)<*∞* for some *λ*=*λ*(*x*)>0 and is metrizable by . Moreover, if or , then ; otherwise, the reverse inequalities hold. We develop the theory of metric spaces, generated by modulars, and extend the results by H. Nakano, J. Musielak, W. Orlicz, Ph. Turpin and others for modulars on linear spaces.

In the paper, the phenomenon of recursion in morphology of Adyghe, a polysynthetic language of Caucaus is considered. We argue that recursion may be allowed to different extents in different parts of the word and be highly constrained exactly in contexts that are considered prototypical for recursion. Hence this property is not as natural as for syntax.

Causative derivation is the least recursable, concrete applicative derivation is the most, and general oblique applicatives and propositional operators occupy an intermediate place. These results are remarkable because they contrast with our intuitions about syntactic recursion.

Similarity searching has a vast range of applications in various fields of computer science. Many methods have been proposed for exact search, but they all suffer from the curse of dimensionality and are, thus, not applicable to high dimensional spaces. Approximate search methods are considerably more efficient in high dimensional spaces. Unfortunately, there are few theoretical results regarding the complexity of these methods and there are no comprehensive empirical evaluations, especially for non-metric spaces. To fill this gap, we present an empirical analysis of data structures for approximate nearest neighbor search in high dimensional spaces. We provide a comparison with recently published algorithms on several data sets. Our results show that small world approaches provide some of the best tradeoffs between efficiency and effectiveness in both metric and non-metric spaces.

We propose a novel approach for solving the approximate nearest neighbor search problem in arbitrary metric spaces. The distinctive feature of our approach is that we can incrementally build a non-hierarchical distributed structure for given metric space data with a logarithmic complexity scaling on the size of the structure and adjustable accuracy probabilistic nearest neighbor queries. The structure is based on a small world graph with vertices corresponding to the stored elements, edges for links between them and the greedy algorithm as base algorithm for searching. Both search and addition algorithms require only local information from the structure. The performed simulation for data in the Euclidian space shows that the structure built using the proposed algorithm has navigable small world properties with logarithmic search complexity at fixed accuracy and has weak (power law) scalability with the dimensionality of the stored data.

The notion of a modular is introduced as follows. A (metric) *modular* on a set *X* is a function *w*:(0,*∞*)×*X*×*X*→[0,*∞*] satisfying, for all *x*,*y*,*z*∈*X*, the following three properties: *x*=*y* if and only if *w*(*λ*,*x*,*y*)=0 for all *λ*>0; *w*(*λ*,*x*,*y*)=*w*(*λ*,*y*,*x*) for all *λ*>0; *w*(*λ*+*μ*,*x*,*y*)≤*w*(*λ*,*x*,*z*)+*w*(*μ*,*y*,*z*) for all *λ*,*μ*>0. We show that, given *x*0∈*X*, the set *X**w*={*x*∈*X*:lim*λ*→*∞**w*(*λ*,*x*,*x*0)=0} is a metric space with metric

Let k be a field of characteristic zero, let G be a connected reductive algebraic group over k and let g be its Lie algebra. Let k(G), respectively, k(g), be the field of k- rational functions on G, respectively, g. The conjugation action of G on itself induces the adjoint action of G on g. We investigate the question whether or not the field extensions k(G)/k(G)^G and k(g)/k(g)^G are purely transcendental. We show that the answer is the same for k(G)/k(G)^G and k(g)/k(g)^G, and reduce the problem to the case where G is simple. For simple groups we show that the answer is positive if G is split of type A_n or C_n, and negative for groups of other types, except possibly G_2. A key ingredient in the proof of the negative result is a recent formula for the unramified Brauer group of a homogeneous space with connected stabilizers. As a byproduct of our investigation we give an affirmative answer to a question of Grothendieck about the existence of a rational section of the categorical quotient morphism for the conjugating action of G on itself.

Let G be a connected semisimple algebraic group over an algebraically closed field k. In 1965 Steinberg proved that if G is simply connected, then in G there exists a closed irreducible cross-section of the set of closures of regular conjugacy classes. We prove that in arbitrary G such a cross-section exists if and only if the universal covering isogeny Ĝ → G is bijective; this answers Grothendieck's question cited in the epigraph. In particular, for char k = 0, the converse to Steinberg's theorem holds. The existence of a cross-section in G implies, at least for char k = 0, that the algebra k[G]G of class functions on G is generated by rk G elements. We describe, for arbitrary G, a minimal generating set of k[G]G and that of the representation ring of G and answer two Grothendieck's questions on constructing generating sets of k[G]G. We prove the existence of a rational (i.e., local) section of the quotient morphism for arbitrary G and the existence of a rational cross-section in G (for char k = 0, this has been proved earlier); this answers the other question cited in the epigraph. We also prove that the existence of a rational section is equivalent to the existence of a rational W-equivariant map T- - - >G/T where T is a maximal torus of G and W the Weyl group.