Negation of binomial coefficients

We extend the concept of a binomial coefficient to all integer values of its parameters. Our approach is purely algebraic, but we show that it is equivalent to the evaluation of binomial coefficients by means of the Γ-function. In particular, we prove that the traditional rule of “negation” is wrong and should be substituted by a slightly more complex rule. We also show that the “cross product” rule remains valid for the extended definition.     

Connecting pairwise and positional election outcomes

General conclusions relating pairwise tallies with positional (e.g., plurality, antiplurality (“vote-for-two”)) election outcomes were previously known only for the Borda Count. While it has been known since the eighteenth century that the Borda and Condorcet winners need not agree, it had not been known, for instance, in which settings the Condorcet and plurality winners can disagree, or must agree. Results of this type are developed here for all three-alternative positional rules. These relationships are based on an easily used method that connects pairwise tallies with admissible positional outcomes; e.g., a special case provides the first necessary and sufficient conditions ensuring that the Condorcet winner is the plurality winner; another case identifies when there must be a profile whereby each candidate is the “winner” with some positional rule.     

Fuzzy logic in measurements

Our main interest in this paper is to translate from “natural language” into “system theoretical language”. This is of course important since a statement in system theory can be analyzed mathematically or computationally. We assume that, in order to obtain a good translation, “system theoretical language” should have great power of expression. Thus we first propose a new frame of system theory, which includes the concepts of “measurement” as well as “state equation”. And we show that a certain statement in usual conversation, i.e., fuzzy modus ponens with the word “very”, can be translated into a statement in the new frame of system theory. Though our result is merely one example of the translation from “natural language” into “system theoretical language”, we believe that our method is fairly general.     

Mereological relations

A “mereological” relation is one of “part-to-whole” type. This paper proposes a model-theoretic approach to identifying and classifying such relations. Three initial applications of this approach are investigated. In each case, the class of identified relations is found to consist precisely of the partial orders on the underlying set. Further applications are proposed.     

A comparison of the monomial method and the S-system method for solving systems of algebraic equations

Two numerical methods for solving systems of equations have recently been proposed: a method based on monomial approximations (the “monomial method”) and a technique based on S-system methodology (the “S-system method”). The two methods have been shown to be fundamentally identical, that is, they are both equivalent to Newton's method operating on a transformed version of the system of equations. Yet, when applied specifically to algebraic systems of equations, they have significant computational differences that may impact the relative computational efficiency of the two methods. These computational differences are described. A combinatorial strategy for locating many, and sometimes all, solutions to a system of nonlinear equations has also been suggested previously. This paper further investigates the effectiveness of this strategy when applied to either of the two methods.     

Generic pairs of SU-rank 1 structures

For a supersimple SU-rank 1 theory T we introduce the notion of a generic elementary pair of models of T (generic T-pair). We show that the theory T^* of all generic T-pairs is complete and supersimple. In the strongly minimal case, T^* coincides with the theory of infinite dimensional pairs, which was used in (S. Buechler, Pseudoprojective strongly minimal sets are locally projective, J. Symbolic Logic 56(4) (1991) 1184–1194) to study the geometric properties of T. In our SU-rank 1 setting, we use T^* for the same purpose. In particular, we obtain a characterization of linearity for SU-rank 1 structures by giving several equivalent conditions on T^*, find a “weak” version of local modularity which is equivalent to linearity, show that linearity coincides with 1-basedness, and use the generic pairs to “recover” projective geometries over division rings from non-trivial linear SU-rank 1 structures.     

Numerical evaluations for shock and discontinuity velocity related to similarity solutions of quasilinear hyperbolic systems

Three problems of physical interest, which are described by first-order quasilinear hyperbolic systems in conservative form, are considered. These systems are invariant with respect to the stretching group of transformations and, more important, they admit an associated group. So we are able to characterize both the profile of the shock and discontinuity velocity; the latter by making use of the concept of “discrete perturbation stability analysis”.     

Statistical learning control of uncertain systems: theory and algorithms

It has recently become clear that many control problems are too difficult to admit analytic solutions. New results have also emerged to show that the computational complexity of some “solved” control problems is prohibitive. Many of these control problems can be reduced to decidability problems or to optimization questions. Even though such questions may be too difficult to answer analytically, or may not be answered exactly given a reasonable amount of computational resources, researchers have shown that we can “approximately” answer these questions “most of the time”, and have “high confidence” in the correctness of the answers.     

Comparing Fleming-Viot and Dawson-Watanabe processes

Fleming-Viot processes and Dawson-Watanabe processes are two classes of “superprocesses” that have received a great deal of attention in recent years. These processes have many properties in common. In this paper, we prove a result that helps to explain why this is so. It allows one to prove certain theorems for one class when they are true for the other. More specifically, we show that product moments of a Fleming-Viot process can be bounded above by the corresponding moments of the Dawson-Watanabe process with the same “underlying particle motion”, and vice versa except for a multiplicative constant. As an application, we establish existence and continuity properties of local time for certain Fleming-Viot processes.     

Generalizing the modeling of fuzzy logic controllers by parameterized aggregation operators

We describe the type of reasoning used in the typical fuzzy logic controller, the Mamdani reasoning method. We point out the basic assumptions in this model. We discuss the S-OWA operators which provide families of parameterized “andlike” and “orlike” operators. We generalize the Mamdani model by introducing these operators. We introduce a method, which we call Direct Fuzzy Reasoning (DFR), which results from one choice of the parameters. We develop some learning algorithms for the new method. We show how the Takagi-Sugeno-Kang (TSK) method of reasoning is an example of this DFR method.     

A quantum mechanical approach to a fuzzy theory

Recently, we proposed a general measurement theory for classical and quantum systems (i.e., “objective fuzzy measurement theory”). In this paper, we propose “subjective fuzzy measurement theory”, which is characterized as the statistical method of the objective fuzzy measurement theory. Our proposal of course has a lot of advantages. For example, we can directly see “membership functions” (= “fuzzy sets”) in this theory. Therefore, we can propose the objective and the subjective methods of membership functions. As one of the consequences, we assert the objective (i.e., individualistic) aspect of Zadeh's theory. Also, as a quantum application, we clarify Heisenberg's uncertainty relation.     

Landmarks in graphs

Navigation can be studied in a graph-structured framework in which the navigating agent (which we shall assume to be a point robot) moves from node to node of a “graph space”. The robot can locate itself by the presence of distinctively labeled “landmark” nodes in the graph space. For a robot navigating in Euclidean space, visual detection of a distinctive landmark provides information about the direction to the landmark, and allows the robot to determine its position by triangulation. On a graph, however, there is neither the concept of direction nor that of visibility. Instead, we shall assume that a robot navigating on a graph can sense the distances to a set of landmarks.

Evidently, if the robot knows its distances to a sufficiently large set of landmarks, its position on the graph is uniquely determined. This suggests the following problem: given a graph, what are the fewest number of landmarks needed, and where should they be located, so that the distances to the landmarks uniquely determine the robot's position on the graph? This is actually a classical problem about metric spaces. A minimum set of landmarks which uniquely determine the robot's position is called a “metric basis”, and the minimum number of landmarks is called the “metric dimension” of the graph. In this paper we present some results about this problem. Our main new results are that the metric dimension of a graph with n nodes can be approximated in polynomial time within a factor of O(log n), and some properties of graphs with metric dimension two.     

Multi-step quasi-Newton methods for optimization

Quasi-Newton methods update, at each iteration, the existing Hessian approximation (or its inverse) by means of data deriving from the step just completed. We show how “multi-step” methods (employing, in addition, data from previous iterations) may be constructed by means of interpolating polynomials, leading to a generalization of the “secant” (or “quasi-Newton”) equation. The issue of positive-definiteness in the Hessian approximation is addressed and shown to depend on a generalized version of the condition which is required to hold in the original “single-step” methods. The results of extensive numerical experimentation indicate strongly that computational advantages can accrue from such an approach (by comparison with “single-step” methods), particularly as the dimension of the problem increases.     

New results on the conjecture of Rhodes and on the topological conjecture

The Conjecture of Rhodes, originally called the “type II conjecture” by Rhodes, gives an algorithm to compute the kernel of a finite semigroup. This conjecture has numerous important consequences and is one of the most attractive problems on finite semigroups. It was known that the conjecture of Rhodes is a consequence of another conjecture on the finite group topology for the free monoid. In this paper, we show that the topological conjecture and the conjecture of Rhodes are both equivalent to a third conjecture and we prove this third conjecture in a number of significant particular cases.     

An experimental comparison of four graph drawing algorithms

In this paper we present an extensive experimental study comparing four general-purpose graph drawing algorithms. The four algorithms take as input general graphs (with no restrictions whatsoever on connectivity, planarity, etc.) and construct orthogonal grid drawings, which are widely used in software and database visualization applications. The test data (available by anonymous ftp) are 11,582 graphs, ranging from 10 to 100 vertices, which have been generated from a core set of 112 graphs used in “real-life” software engineering and database applications. The experiments provide a detailed quantitative evaluation of the performance of the four algorithms, and show that they exhibit trade-offs between “aesthetic” properties (e.g., crossings, bends, edge length) and running time.     

Component commonality via hierarchical orthogonal arrays and detailing economic decision matrices

Component commonality (CC) implies products using many common parts, desensitized to the range of product applications (noise), and meeting the functionality objectives of the product line. This paper lists a nine-step methodology for developing CC and applies it to a problem. These steps utilize the major concepts of analytical modeling, economic decision matrices (EDM), quality loss functions (QLS) for variates and weighted utilities, stochastic models, finite element (FE) simulations for concurrent engineering, and statistical design of experiments (DOE) for uncertainty in either application, statistics or managerial decisions. The details of the first six steps were illustrated in a previous paper by application to a problem involving a slider link subjected to an extreme range of “noise” (various inertia/pressure loadings). Six candidate designs of steel, aluminum and titanium were generated using an analytical model and a sensitivity study. The DOE utilized Taguchi's orthogonal arrays. These designs were ranked using cost, weight, and factors of safety with respect to yielding. A refining EDM with a three-part robustness criteria selected two candidates (best was steel, followed by aluminum) considering inner noise in the managerial decisions. In the current paper, the last three steps of the nine-step methodology are applied to these two candidates in order to obtain the “optimal” part for CC. The FE stress results are used with a modified Goodman fatigue criteria, and a stochastic model is developed based upon beta (strength) and three-parameter Weibull (stress) distributions. The model is then used in a detailing EDM to determine the stochastic reliability associated with a QLS defined with respect to fatigue reliability. A “fine-tuned” aluminum candidate is shown to meet a priori reliability requirements and have low-quality losses. However, both original candidates exhibited some high-quality losses, even though such losses were acceptable in the preceding refining EDM. The authors demonstrate that this loss of quality can be prevented if a fatigue criteria is used in both the refining and detailing EDM stages of the design process and, “warranty failures” are based on stochastic rather than deterministic definitions of maximum environmental conditions.     

Construction of the value function in a pursuit-evasion game with three pursuers and one evader

A differential pursuit-evasion game is considered with three pursuers and one evader. It is assumed that all objects (players) have simple motions and that the game takes place in a plane. The control vectors satisfy geometrical constraints and the evader has a superiority in control resources. The game time is fixed. The value functional is the distance between the evader and the nearest pursuer at the end of the game. The problem of determining the value function of the game for any possible position is solved.

Three possible cases for the relative arrangement of the players at an arbitrary time are studied: “one-after-one”, “two-after-one”, “three-after-one-in-the-middle” and “three-after-one”. For each of the relative arrangements of the players a guaranteed result function is constructed. In the first three cases the function is expressed analytically. In the fourth case a piecewise-programmed construction is presented with one switchover, on the basis of which the value of the function is determined numerically. The guaranteed result function is shown to be identical with the game value function. When the initial pursuer positions are fixed in an arbitrary manner there are four game domains depending on their relative positions. The boundary between the “three-after-one-in-the-middle” domain and the “three-after-one” domain is found numerically, and the remaining boundaries are interior Nicomedean conchoids, lines and circles. Programs are written that construct singular manifolds and the value function level lines.     

Goodness-of-Fit Tests Based on Sample Space Partitions: A Unifying Overview

Recently the authors have proposed tests for the one-sample and the k-sample problem, and a test for independence. All three tests are based on sample space partitions, but they were originally developed in di_erent papers. Here we give an overview of the construction of these tests, stressing the common underlying concept of “sample space partitions.”     

“Drawings since hit tables in lotteries” and a new multivariate geometric distribution

In number lotteries people choose r numbers out of s. Weekly published “drawings since hit tables” indicate how many drawings have taken place since each of the s numbers was last selected as a winning number. Among many lotto players, they enhance the widespread belief that numbers should be “due” if they have not come up for a long time. Under the assumptions of independence of the drawings and equiprobability of all possible combinations, the random s-vectors Y_n, n 1, of entries in a drawings since hit table after n drawings form a Markov chain. The limit distribution of Y_n as n → ∞ is a new multivariate generalization of the geometric distribution. The determination of the distribution of the maximum entry in a drawings since hit table within the first n draws of a lottery seems to be an open problem.     

Representing probability measures using probabilistic processes

In the Type-2 Theory of Effectivity, one considers representations of topological spaces in which infinite words are used as “names” for the elements they represent. Given such a representation, we show that probabilistic processes on infinite words, under which each successive symbol is determined by a finite probabilistic choice, generate Borel probability measures on the represented space. Conversely, for several well-behaved types of space, every Borel probability measure is represented by a corresponding probabilistic process. Accordingly, we consider probabilistic processes as providing “probabilistic names” for Borel probability measures. We show that integration is computable with respect to the induced representation of measures.