Recognizing polygonal parts from width measurements

Automatic recognition of parts is an important problem in many industrial applications. One model of the problem is: given a finite set of polygonal parts, use a set of “width” measurements taken by a parallel-jaw gripper to determine which part is present. We study the problem of computing efficient strategies (“grasp plans”), with the goal to minimize the number of measurements necessary in the worst case. We show that finding a minimum length grasp plan is -hard, and give a polynomial time approximation algorithm that is simple and produces a solution that is within a log factor from optimal.     

A theory of tensor products for module categories for a vertex operator algebra, III

This is the third part in a series of papers developing a tensor product theory for modules for a vertex operator algebra. The goal of this theory is to construct a “vertex tensor category” structure on the category of modules for a suitable vertex operator algebra. The notion of vertex tensor category is essentially a “complex analogue” of the notion of symmetric tensor category, and in fact a vertex tensor category produces a braided tensor category in a natural way. In this paper, we focus on a particular element P(z) of a certain moduli space of three-punctured Riemann spheres; in general, every element of this moduli space will give rise to a notion of tensor product, and one must consider all these notions in order to construct a vertex tensor category. Here we present the fundamental properties of the P(z)-tensor product of two modules for a vertex operator algebra. We give two constructions of a P(z)-tensor product, using the results, established in Parts I and II of this series, for a certain other element of the moduli space. The definitions and results in Parts I and II are recalled.     

Drawing series parallel digraphs symmetrically

In this paper we present algorithms for drawing series parallel digraphs with as much symmetry as possible. The first step is to compute a certain kind of automorphism, called an “upward planar automorphism” for an input series parallel digraph. The next step uses these automorphisms to construct a symmetric drawing of the graph. We present several variations of the second step, with visibility drawings, “bus-orthogonal” drawings, and polyline drawings. All algorithms run in linear time.     

Trajectories of lattice particles using the new approach to no integrability

We study two systems which lead to a lattice when an integration path is specified in “aesthetic field theory”. One of these cases involves nonsoliton type particles (magnitudes of maxima and minima oscillate in time). The other system is made up of soliton type particles. The two systems are intrinsically three-dimensional. We speak of the third dimension as “time”. In one of our solutions, the particles move on straight line trajectories, insofar as our numerical work indicates. In the other solution, the soliton type particles undergo what appears to be simple harmonic motion in both the x- and y-directions (loop motion). We then study these two systems using the new approach to integrability which involves a superposition principle and is characterized by a unique change function at each point. We still find multi maxima and minima. The systems are not as symmetric as the lattice. The soliton characteristic is preserved by the new method. We investigated the motion of lattice particles. We found evidence of maxima (minima) regions coalescing so that the location of the maxima (minima) became difficult to follow. The concept of location of particles may not even have a well-defined meaning here. We find examples of soliton particles appearing and disappearing. We conclude that the manner of integration in a no integrability theory can transform a system with well-defined trajectories into a system where particles can no longer be followed in time.     

A greedy-algorithm characterization of valuated Δ-matroids

We study a variant of the greedy algorithm for weight functions defined on the system of subsets of a given finite set E and show that this algorithm works exactly for “valuated Δ-matroids.” Examples come from valuation theory.     

The rate of convergence for the cyclic projections algorithm III: Regularity of convex sets

The cyclic projections algorithm is an important method for determining a point in the intersection of a finite number of closed convex sets in a Hilbert space. That is, for determining a solution to the “convex feasibility” problem. This is the third paper in a series on a study of the rate of convergence for the cyclic projections algorithm. In the first of these papers, we showed that the rate could be described in terms of the “angles” between the convex sets involved. In the second, we showed that these angles often had a more tractable formulation in terms of the “norm” of the product of the (nonlinear) metric projections onto related convex sets.In this paper, we show that the rate of convergence of the cyclic projections algorithm is also intimately related to the “linear regularity property” of Bauschke and Borwein, the “normal property” of Jameson (as well as Bakan, Deutsch, and Li’s generalization of Jameson’s normal property), the “strong conical hull intersection property” of Deutsch, Li, and Ward, and the rate of convergence of iterated parallel projections. Such properties have already been shown to be important in various other contexts as well.     

The Marotto Theorem on planar monotone or competitive maps

In 1978, Marotto generalized Li–Yorke’s results on the criterion for chaos from one-dimensional discrete dynamical systems to n-dimensional discrete dynamical systems, showing that the existence of a non-degenerate snap-back repeller implies chaos in the sense of Li–Yorke. This theorem is very useful in predicting and analyzing discrete chaos in multi-dimensional dynamical systems. Yet, besides it is well known that there exists an error in the conditions of the original Marotto Theorem, and several authors had tried to correct it in different way, Chen, Hsu and Zhou pointed out that the verification of “non-degeneracy” of a snap-back repeller is the most difficult in general and expected, “almost beyond reasonable doubt,” that the existence of only degenerate snap-back repeller still implies chaotic, which was posed as a conjecture by them. In this paper, we shall give necessary and sufficient conditions of chaos in the sense of Li–Yorke for planar monotone or competitive discrete dynamical systems and solve Chen–Hsu–Zhou Conjecture for such kinds of systems.     

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.     

A unifying look at the Apostolico–Giancarlo string-matching algorithm

String matching is the problem of finding all the occurrences of a pattern in a text. We present a new method to compute the combinatorial shift function (“matching shift”) of the well-known Boyer–Moore string matching algorithm. This method implies the computation of the length of the longest suffixes of the pattern ending at each position in this pattern. These values constituted an extra-preprocessing for a variant of the Boyer–Moore algorithm designed by Apostolico and Giancarlo. We give here a new presentation of this algorithm that avoids extra preprocessing together with a tight bound of 1.5n character comparisons (where n is the length of the text).     

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.     

Students' Critical Awareness of Voice and Agency in Mathematics Classroom Discourse

This account of my extended conversation with a high school mathematics class focuses on voice and agency. As an investigation of possibilities opened up by introducing mathematics students to what Fairclough (1992) called “critical language awareness” (p. 2), I prompted the students daily to become ever more aware of their language practices in class. The tensions in this conversation proved parallel to the tension in mathematics between individual initiative and convention, a tension that Pickering (1995) called the “dance of agency” (p. 21). Participant students in this classroom-based research resisted the idea of linguistic reference to human agency, although their actual language practice revealed some recognition of human agency.     

Universal deformation formulas and breaking symmetry

We show that an algebra with a non-nilpotent Lie group of automorphisms or “symmetries” (e.g., smooth functions on a manifold with such a group of diffeomorphisms) may generally be deformed (in the function case, “quantized”) in such a way that only a proper subgroup of the original group acts. This symmetry breaking is a consequence of the existence of certain “universal deformation formulas” which are elements, independent of the original algebra, in the tensor algebra of the enveloping algebra of the Lie algebra of the group.     

Nondeterministic dynamic programming on a parallel coprocessing system

We describe how nondeterministic dynamic programming (DP) algorithms can be designed for a new class of parallel coprocessing systems using “functional memory”, an architecture based upon dataflow computer principles. We also show how Petri nets can be used to model and express such parallel DP algorithms. Finally, we discuss architectural improvements that would facilitate the processing of Petri net models of nondeterministic DP algorithms on functional memory computers (FMC).     

A cycle augmentation algorithm for minimum cost multicommodity flows on a ring

Minimum cost multicommodity flows are a useful model for bandwidth allocation problems. These problems are arising more frequently as regional service providers wish to carry their traffic over some national core network. We describe a simple and practical combinatorial algorithm to find a minimum cost multicommodity flow in a ring network. Apart from 1 and 2-commodity flow problems, this seems to be the only such “combinatorial augmentation algorithm” for a version of exact mincost multicommodity flow. The solution it produces is always half-integral, and by increasing the capacity of each link by one, we may also find an integral routing of no greater cost. The “pivots” in the algorithm are determined by choosing an >0, increasing and decreasing sets of variables, and adjusting these variables up or down accordingly by . In this sense, it generalizes the cycle cancelling algorithms for (single source) mincost flow. Although the algorithm is easily stated, proof of its correctness and polynomially bounded running time are more complex.     

The Borda rule and Pareto stability: a further comment

In their paper “The Borda rule and Pareto stability: a comment” published in 1979 by Econometrica, Farkas and Nitzan revealed the “intimate relationship” between the Borda rule and the Pareto criterion. The idea was the following: in a profile of total orders, when there is a candidate who obviously wins under unanimous agreement of the voters, that candidate should be in the choice set. In a profile where there is no obvious winner, the candidates that are the closest to unanimity should be chosen. According to this principle, they defined a choice rule called “closeness to unanimity” and they showed that it is equivalent to the Borda rule. In our paper, we give an equivalent result for a ranking rule. Then we try to obtain similar results when aggregating profiles of tournaments, weak orders, semiorders, fuzzy relations, … and we show that the definition of an obvious winner is no more obvious.     

C*-bialgebra Defined as the Direct Sum of UHF Algebras

Let 𝒜₀(*) denote the direct sum of a certain set of uniformly hyperfinite (UHF) algebras, and let 𝒜(*) ≡ C ⊕ 𝒜₀(*). We introduce a non-cocommutative comultiplication Δ_? on 𝒜(*), and give an example of comodule-C*-algebra of the C*-bialgebra (𝒜(*), Δ_?). With respect to Δ_?, we define a nonsymmetric tensor product of *-representations of UHF algebras and show tensor product formulas of Gel'fand–Na\u?mark–Segal (GNS) representations by product states.     

On quasi-strongly regular graphs

We study the quasi-strongly regular graphs, which are a combinatorial generalization of the strongly regular and the distance regular graphs. Our main focus is on quasi-strongly regular graphs of grade 2. We prove a “spectral gap”-type result for them which generalizes Seidel's well-known formula for the eigenvalues of a strongly regular graph. We also obtain a number of necessary conditions for the feasibility of parameter sets and some structural results. We propose the heuristic principle that the quasi-strongly regular graphs can be viewed as a “lower-order approximation” to the distance regular graphs. This idea is illustrated by extending a known result from the distance-regular case to the quasi-strongly regular case. Along these lines, we propose a number of conjectures and open problems. Finally, we list the all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.     

Multiple bifurcation from “simple” eigenvalues

Consider an operator equation G(u,λ) = 0 where λ is a real parameter. Suppose 0 is a “simple” eigenvalue of the Fréchet derivative G_u at (u₀, λ₀). We give a hierarchy of conditions which completely determines the solution structure of the operator equation. It will be shown that multiple bifurcation as well as simple bifurcation can occur. This extends the standard bifurcation theory from a simple eigenvalue in which only one branch bifurcates. We also discuss limit point bifurcations. Applications to semilinear elliptic equations and the homotopy method for the matrix eigenvalue problem are also given.     

Cut-threshold graphs

We study the structure of the networks in which connectedness and disconnectedness can be expressed by a threshold system. This means that the elements of the network have a certain “destruction cost” and that the enemy can disconnect the network if and only if they pay a large enough price. We give polynomial algorithms for the recognition of such networks, and for the determination of the appropriate costs and threshold value.     

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.