Finding the optimal metric in classification problems with ordinal features

A method for finding the optimal distance function for the classification problem with two classes in which the objects are specified by vectors of their ordinal features is proposed. An optimal distance function is sought by the minimization of the weighted difference of the average intraclass and interclass distances. It is assumed that a specific distance function is given for each feature, which is defined on the Cartesian product of the set of integer numbers in the range from 0 to N − 1 and takes values from 0 to M. Distance functions satisfy modified metric properties. The number of admissible distance functions is calculated, which enables one to significantly reduce the complexity of the problem. To verify the appropriateness of metric optimization and to perform experiments, the nearest neighbor algorithm is used.     

A new efficient approach to the characterization of D‐stable matrices

The concept of D‐stability is relevant for stable square matrices of any order, especially when they appear in ordinary differential systems modeling physical problems. Indeed, D‐stability was treated from different points of view in the last 50 years, but the problem of characterization of a general D‐stable matrix was solved for low‐order matrices only (ie, up to order 4). Here, a new approach is proposed within the context of numerical linear algebra. Starting from a known necessary and sufficient condition, other simpler equivalent necessary and sufficient conditions for D‐stability are proved. Such conditions turn out to be computationally more appealing for symbolic software, as discussed in the reported examples. Therefore, a new symbolic method is proposed to characterize matrices of order greater than 4, and then it is used in some numerical examples, given in details.     

A Note on Binary Plane Partitions

   Abstract. This paper considers binary space partition s (BSP for short) for disjoint line segments in the plane. The BSP for a disjoint set of objects is a scheme dividing the space recursively by hyperplanes until the resulting fragments of objects are separated. The size of a BSP is the number of resulting fragments of the objects. We show that the minimal size of a BSP for n disjoint line segments in the plane is Ω (n log n /log log n) in the worst case.     

Maximization and minimization in problems involving the bi-Laplacian

This paper concerns minimization and maximization of the energy integral in problems involving the bi-Laplacian under either homogeneous Navier boundary conditions or homogeneous Dirichlet boundary conditions. Physically, in case of N = 2, our equation models the equilibrium configuration of a non-homogeneous plate Ω which is either hinged or clamped along the boundary. Given several materials (with different densities) of total extension |Ω|, we investigate the location of these materials inside Ω so to maximize or minimize the energy integral of the corresponding plate.     

Local regularity for nonlocal equations with variable exponents

In this paper, we study local regularity properties of minimizers of nonlocal variational functionals with variable exponents and weak solutions to the corresponding Euler–Lagrange equations. We show that weak solutions are locally bounded when the variable exponent p is only assumed to be continuous and bounded. Furthermore, we prove that bounded weak solutions are locally Hölder continuous under some additional assumptions on p. On the one hand, the class of admissible exponents is assumed to satisfy a log-Hölder–type condition inside the domain, which is essential even in the case of local equations. On the other hand, since we are concerned with nonlocal problems, we need an additional assumption on p outside the domain.     

Conceptualism and the Problem of Illusory Experience

According to the conceptualist view in the philosophy of perception, we possess concepts for all the objects, properties, and relations which feature in our experiences. Richard Heck has recently argued that the phenomenon of illusory experience provides us with conclusive reasons to reject this view. In this paper, I examine Heck’s argument, I explain why I think that Bill Brewer’s conceptualist response to it is ineffective, and I then outline an alternative conceptualist response which I myself endorse. My argument turns on the fact that both Heck, in constructing his objection to conceptualism, and Brewer, in responding to it, miss a crucial distinction between perceptual demonstrative concepts of objects, on the one hand, and perceptual demonstrative concepts of properties, on the other.

Explicit Solution of a Quorum Queueing System

This paper deals with the queueing system M/G ^r /1 in which customers are served in batches of fixed size r. The author considers the discrete time parameter process, an embedded Markov chain, and the continuous time parameter process, a semi-regenerative process. In both cases, explicit solutions are given for the system size steady-state probabilities in terms of the zeros, inside and/or outside the closed unit ball, of the characteristic equation. Moments are derived and illustrative examples are provided.     

Matrix completion problems of block type

The solvability, either unconditional or under certain conditions, is proved for three matrix completion problems of block type. Being a problem of block type means that a matrixA must be constructed with a prescribed characteristic polynomial and one or several blocks in a 2 × 2 partition also prescribed. For the problems under analysis, one prescribes, respectively, (a) the blockA ₁₂; (b) the blockA ₁₁; (c) the blocksA ₁₁ andA ₁₂. We discuss our experience in implementing the algorithms that solve the problems above as procedures in the symbolic computation system MAPLE. Translated fromMatematicheskie Zametki, Vol. 67, No. 6, pp. 863–873, June, 2000. The first author was supported by the Russian Foundation for Basic Research under grant No. 97-01-00927.     

RGC: A new conceptual clustering algorithm for mixed incomplete data sets

In this paper, a new conceptual algorithm for the conceptual analysis of mixed incomplete data sets is introduced. This is a logical combinatorial pattern recognition (LCPR) based tool for the conceptual structuralization of spaces. Starting from the limitations of the elaborated conceptual algorithms, our laboratories are working in the application of the methods, the techniques, and in general, the philosophy of the logical combinatorial pattern recognition with the task to improve those limitations. An extension of Michalski's concept of l-complex for any similarity measure, a generalization operator for symbolic variables, and an extension of Michalski's refunion operator are introduced. Finally, the performance of the RGC algorithm is analyzed. A comparison with several known conceptual algorithms is presented.     

Leray’s inequality in general multi-connected domains in {\mathbb{R}^n}

Consider the stationary Navier–Stokes equations in a bounded domain whose boundary consists of L + 1 smooth (n − 1)-dimensional closed hypersurfaces Γ₀, Γ₁, . . . , Γ _L , where Γ₁, . . . , Γ _L lie inside of Γ₀ and outside of one another. The Leray inequality of the given boundary data β on plays an important role for the existence of solutions. It is known that if the flux on Γ _i (ν: the unit outer normal to Γ _i ) is zero for each i = 0, 1, . . . , L, then the Leray inequality holds. We prove that if there exists a sphere S in Ω separating in such a way that Γ₁, . . . , Γ _k (1 ≦ k ≦ L) are contained inside of S and that the others Γ _k+1, . . . , Γ _L are outside of S, then the Leray inequality necessarily implies that γ ₁ + · · · +  γ _k =  0. In particular, suppose that there are L spheres S ₁, . . . , S _L in Ω lying outside of one another such that Γ _i lies inside of S _i for all i = 1, . . . , L. Then the Leray inequality holds if and only if γ ₀ = γ ₁ = · · · = γ _L = 0.     

Linear systems, singularity and not too ramified morphisms

Given a smooth k-variety Y (where k is a field of arbitrary characteristic) and a linear systemL on Y we study the dimension of the singular locus of the general element ofL, both inside and outside the base locus B ofL. We interpret these results from the point of view of the transversality theory, and we improve a result by Speiser about the not too ramified morphisms. Moreover, we show that our results can be applied in some cases where a criterion by Zhang, for the smoothness of the general element ofL, fails. Entrata in Redazione il 15 settembre 1997, e in versione definitiva il 28 ottobre 1999.     

Equilibrium probability calculations for a discrete-time bulk queue model

Many problems in management science and telecommunications can be solved by the analysis of aD ^X/D^m/1 queueing model. In this paper, we use the zeros, both inside and outside the unit circle, of the denominator of the generating function of the model to obtain an explicit closed-form solution for the equilibrium probabilities of the number of customers in the system. The moments of the number of customers in the queue or in the system are also studied. When there are infinitely many zeros outside the unit circle, we propose an approximation method using polynomials. This method yields correct values for a finite number of the probabilities, the number depending on the degree of the polynomial approximation.     

Symbolic Computation with Indexed Objects within MATHEMATICA

The new Mathematica package EinS is intended for calculations involving sums of indexed objects (e.g., tensors). EinS automatically handles implicit summations and dummy indices, allows one to assign symmetry properties to new objects, and has an efficient built-in simplification algorithm based on pattern matching. Further features include printing expressions in a two-dimensional form, exporting into plain TeX or LaTeX with user-controllable alignment commands, converting implicit summations into explicit ones, debugging capabilities, and online help messages. Some typical applications of EinS are described. Bibliography: 17 titles.     

Supersymmetric Quantum Field Theory: Indefinite Metric

We study the recently introduced Krein structure (indefinite metric) of the N = 1 supersymmetry and present the way into physical applications outside path integral methods. From the mathematical point of view some perspectives are mentioned at the end of the paper.     

Space Efficient Suffix Trees

We give first the representation of a suffix tree that uses n lg n + O(n) bits of space and supports searching for a pattern string in the given text (from a fixed size alphabet) in O(m) time, where n is the size of the text and m is the length of the pattern. The structure is quite simple and answers a question raised by Muthukrishnan (in Proceedings of the FST and TCS Preconference Workshop on Randomization, 1997, pp. 23–27). Previous compact representations of suffix trees had either a higher lower order term in space and had some expectation assumption or required more time for searching. When the size of the alphabet k is not viewed as a constant, this structure can be modified to use the same space but take O(m lg k) time for string searching or to use an additional O(n lg k) bits but take the same O(m) time for searching. We then give several index structures for binary texts, with less space including

• a structure that uses a suffix array (lg  bits) and an additional () bits,

• an indexing structure that takes bits of space, and

• an ( lg ) bit structure which answers in () time, the decision question of whether a given pattern of length occurs in the text.

Each of these structures uses a different technique, either in the storage scheme or in the search algorithm, in reducing the space requirement. The first one uses a suffix array, a sparse suffix tree, and a table structure. Finding all the occurrences of a pattern using this structure takes O(m + s) time, where s is the number of occurrences of the pattern in the text. The second structure constructs a sparse suffix tree for all the suffixes that start with the bit that occurs more times in the given binary text. The last structure uses an iterative algorithm to search for the pattern. This structure is the first o(n lg n) bit index to support the decision version of indexing queries in time linear in the length of the pattern. But this does not support the general indexing queries where we want to find the position of the occurrence of the pattern.Our main contribution is the development of techniques to use the succinct tree representation through balanced parentheses for suffix trees.     

A Property of Sobolev Spaces and Existence in Optimal Design

   Abstract. We prove that for bounded open sets Ω with continuous boundary, Sobolev spaces of type W ₀ ^l,p (Ω ) are characterized by the zero extension outside of Ω . Combining this with a compactness result for domains of class C, we obtain a general existence theorem for shape optimization problems governed by nonlinear nonhomogenous Dirichlet boundary value problems of arbitrary order, in arbitrary dimension and with general cost functionals.     

A projected discrete Gronwall's inequality with sub-exponential growth

Along with the increasing interest in (h, k)-dichotomy, more attentions are paid to sub-exponential growth in research of asymptotic behaviours. In this paper, we generalize a projected discrete Gronwall's inequality given in [J. Differ. Equ. Appl. 10 (2004), 661–689] to a general one, which may include both terms of sub-exponential growth inside the summation and non-monotonic terms outside the summation. We demonstrate our results with concrete non-monotonic functions and sub-exponential functions. We apply our results to estimating bounded solutions of a non-linear difference equation with an (h, k)-dichotomy.     

Kinetically constrained spin models

We analyze the density and size dependence of the relaxation time for kinetically constrained spin models (KCSM) intensively studied in the physics literature as simple models sharing some of the features of the glass transition. KCSM are interacting particle systems on with Glauber-like dynamics, reversible w.r.t. a simple product i.i.d Bernoulli(p) measure. The essential feature of a KCSM is that the creation/destruction of a particle at a given site can occur only if the current configuration around it satisfies certain constraints which completely define each specific model. No other interaction is present in the model. From the mathematical point of view, the basic issues concerning positivity of the spectral gap inside the ergodicity region and its scaling with the particle density p remained open for most KCSM (with the notably exception of the East model in d = 1; Aldous and Diaconis in J Stat Phys 107(5–6):945–975, 2002). Here for the first time we: (i) identify the ergodicity region by establishing a connection with an associated bootstrap percolation model; (ii) develop a novel multi-scale approach which proves positivity of the spectral gap in the whole ergodic region; (iii) establish, sometimes optimal, bounds on the behavior of the spectral gap near the boundary of the ergodicity region and (iv) establish pure exponential decay at equilibrium for the persistence function, i.e. the probability that the occupation variable at the origin does not change before time t. Our techniques are flexible enough to allow a variety of constraints and our findings disprove certain conjectures which appeared in the physical literature on the basis of numerical simulations.      

Probabilist,possibilist and belief objects for knowledge analysis

The main aim of the symbolic approach in data analysis is to extend problems, methods and algorithms used on classical data to more complex data called symbolic objects which are well adapted to representing knowledge and which are generic unlike usual observations which characterize individual things. We introduce several kinds of symbolic objects: Boolean, possibilist, probabilist and belief. We briefly present some of their qualities and properties; three theorems show how Probability, Possibility and Evidence theories may be extended on these objects. Finally, four kinds of data analysis problems including the symbolic extension are illustrated by several algorithms which induce knowledge from classical data or from a set of symbolic objects.