The dynamic clusters method in nonhierarchical clustering

Given a finite setE R ⁿ, the problem is to find clusters (or subsets of similar points inE) and at the same time to find the most typical elements of this set. An original mathematical formulation is given to the problem. The proposed algorithm operates on groups of points, called samplings (samplings may be called multiple centers or cores); these samplings adapt and evolve into interesting clusters. Compared with other clustering algorithms, this algorithm requires less machine time and storage. We provide some propositions about nonprobabilistic convergence and a sufficient condition which ensures the decrease of the criterion. Some computational experiments are presented.     

An efficient parallel algorithm for computing a large independent set in a planar graph

Let (G) denote the independence number of a graphG, that is the maximum number of pairwise independent vertices inG. We present a parallel algorithm that computes in a planar graphG = (V, E), an independent set such that ¦I¦ (G)/2. The algorithm runs in timeOlog² n) and requires a linear number of processors. This is achieved by denning a new set of reductions that can be executed locally and simultaneously; furthermore, it is shown that a constant fraction of the vertices in the graph are reducible. This is the best known approximation scheme when the number of processors available is linear; parallel implementation of known sequential algorithms requires many more processors.Joseph Naor was supported by Contract ONR N00014-88-K-0166. Most of this work was done while he was a post-doctoral fellow at the Department of Computer Science, University of Southern California, Los Angeles, CA 90089-0782, USA.     

Applications of the crossing number

LetG be a graph ofn vertices that can be drawn in the plane by straight-line segments so that nok+1 of them are pairwise crossing. We show thatG has at mostc _k nlog^2k–2 n edges. This gives a partial answer to a dual version of a well-known problem of Avital-Hanani, Erdós, Kupitz, Perles, and others. We also construct two point sets {p ₁,,p _n }, {q ₁,,q _n } in the plane such that any piecewise linear one-to-one mappingfR ²R ² withf(pi)=qi (1in) is composed of at least (n ²) linear pieces. It follows from a recent result of Souvaine and Wenger that this bound is asymptotically tight. Both proofs are based on a relation between the crossing number and the bisection width of a graph.The first author was supported by NSF Grant CCR-91-22103, PSC-CUNY Research Award 663472, and OTKA-4269. An extended abstract of this paper was presented at the 10th Annual ACM Symposium on Computational Geometry, Stony Brook, NY, 1994.     

On the Noninteger Polyhedron Vertices of the Three-index Axial Transportation Problem

For the three-index axial transportation polyhedron defined by the integer vector, existence of noninteger vertices was proved. In particular, the three-index n × m × k axial transportation polyhedron having vertices with r fractional components was shown to exist for and only for any number r {4,6,7,...,(n, m, k)}, where (n, m, k) = min{n, m + k - 2} + m + k - 2, n m k 3.     

A semidynamic construction of higher-order voronoi diagrams and its randomized analysis

Thek-Delaunay tree extends the Delaunay tree introduced in [1], and [2]. It is a hierarchical data structure that allows the semidynamic construction of the higher-order Voronoi diagrams of a finite set ofn points in any dimension. In this paper we prove that a randomized construction of thek-Delaunay tree, and thus of all the orderk Voronoi diagrams, can be done inO(n logn+k ³n) expected time and O(k²n) expected storage in the plane, which is asymptotically optimal for fixedk. Our algorithm extends tod-dimensional space with expected time complexityO(k ^(d+1)/2+1 n ^(d+1)/2) and space complexityO(k ^(d+1)/2 n ^(d+1)/2). The algorithm is simple and experimental results are given.This work has been supported in part by the ESPRIT Basic Research Action No. 3075 (ALCOM).     

The plane with parallel coordinates

By means ofParallel Coordinates planar graphs of multivariate relations are obtained. Certain properties of the relationship correspond tothe geometrical properties of its graph. On the plane a point line duality with several interesting properties is induced. A new duality betweenbounded and unbounded convex sets and hstars (a generalization of hyperbolas) and between Convex Unions and Intersections is found. This motivates some efficient Convexity algorithms and other results inComputational Geometry. There is also a suprising cusp inflection point duality. The narrative ends with a preview of the corresponding results inR ^N .     

Gradually intractable problems and nondeterministic log-space lower bounds

The paper places five different problems (thek-pebble game problem, two problems aboutk finite automata, the reachability problem for Petri nets withk tokens, and the teachability problem for graphs whose k-dimensional edge sets are described by Cartesian products ofk factors) into the hierarchyNL _k of problems solvable by nondeterministic Turing machines ink-log₂ n space (and binary tape alphabet, to avoid tape speed-up). The results, when combined with the conjecture thatNL _i contains problems that requireO(n ^k ) deterministic time, show that these problems, while inP for every fixed value ofk, have polynomial deterministic time complexities with the degree of the polynomial growing linearly with the parameterk, and hence are, in this sense, gradually intractable.     

Simple adaptive stabilization of output feedback stabilizable distributed parameter systems

We show that the simple universal adaptive control lawu(t)=N(k(t))y(t)=|y(t)| ², withN(k)=(logk) cos((logk)) and 3+<1, stabilizes all detectable and stabilizable infinite dimensional systems of Pritchard-Salamon type which are externally stabilized by somescalar output feedback. The same controller is also shown to stabilize time varying systems satisfying the same type of output feedback stabilizability.     

On the geodesic voronoi diagram of point sites in a simple polygon

Given a simple polygon withn sides in the plane and a set ofk point sites in its interior or on the boundary, compute the Voronoi diagram of the set of sites using the internal geodesic distance inside the polygon as the metric. We describe anO((n + k) log(n + k) logn)-time algorithm for solving this problem and sketch a fasterO((n + k) log(n + k)) algorithm for the case when the set of sites includes all reflex vertices of the polygon in question.Work on this paper was performed while the author held an AT&T Bell Laboratories Ph.D. Scholarship at New York University.     

How to find Steiner minimal trees in euclideand-space

This paper has two purposes. The first is to present a new way to find a Steiner minimum tree (SMT) connectingN sites ind-space,d >- 2. We present (in Appendix 1) a computer code for this purpose. This is the only procedure known to the author for finding Steiner minimal trees ind-space ford > 2, and also the first one which fits naturally into the framework of backtracking and branch-and-bound. Finding SMTs of up toN = 12 general sites ind-space (for anyd) now appears feasible.We tabulate Steiner minimal trees for many point sets, including the vertices of most of the regular and Archimedeand-polytopes with <- 16 vertices. As a consequence of these tables, the Gilbert-Pollak conjecture is shown to be false in dimensions 3–9. (The conjecture remains open in other dimensions; it is probably false in all dimensionsd withd 3, but it is probably true whend = 2.)The second purpose is to present some new theoretical results regarding the asymptotic computational complexity of finding SMTs to precision .We show that in two-dimensions, Steiner minimum trees may be found exactly in exponential time O(C ^N ) on a real RAM. (All previous provable time bounds were superexponential.) If the tree is only wanted to precision , then there is an (N/)^O(N)-time algorithm, which is subexponential if 1/ grows only polynomially withN. Also, therectilinear Steiner minimal tree ofN points in the plane may be found inN ^O(N) time.J. S. Provan devised an O(N ⁶/⁴)-time algorithm for finding the SMT of a convexN-point set in the plane. (Also the rectilinear SMT of such a set may be found in O(N ⁶) time.) One therefore suspects that this problem may be solved exactly in polynomial time. We show that this suspicion is in fact true—if a certain conjecture about the size of Steiner sensitivity diagrams is correct.All of these algorithms are for a real RAM model of computation allowing infinite precision arithmetic. They make no probabilistic or other assumptions about the input; the time bounds are valid in the worst case; and all our algorithms may be implemented with a polynomial amount of space. Only algorithms yielding theexact optimum SMT, or trees with lengths (1 + ) × optimum, where is arbitrarily small, are considered here.     

On the valuedness of finite transducers

Summary We investigate the valuedness of finite transducers in connection with their inner structure. We show: The valuedness of a finite-valued nondeterministic generalized sequential machine (NGSM) M with n states and output alphabet is at most the maximum of (1-1/#) · (2 ^k ₁ · k ₃ ) ⁿ · n ⁿ ·# ^{n 3 ·k} ₄ / ³ and 1/#·(2 ^k ₂ ·k ₃ ·(1+k ₄ )) ⁿ ·n ⁿ where k ₁6.25 and k ₂11.89 are constants and k ₃1 and k ₄0 are local structural parameters of M. There are two simple criteria which characterize the infinite valuedness of an NGSM. By these criteria, it is decidable in polynomial time whether or not an NGSM is infinite-valued. In both cases, # > 1 and # = 1, the above upper bound for the valuedness is almost optimal. By reduction, all results can be easily generalized to normalized finite transducers.     

Iterated linear control and iterated one-turn pushdowns

For a class of languages, an-controlled linear grammarK consists of a linear context-free grammarG and a control languageH in, where the terminals ofH are interpreted as the labels of rules ofG. The language generated byK is obtained by derivations ofG such that the corresponding strings of labels of the rules applied are control strings inH. The control of linear grammars can be iterated by starting with and by taking the result of thekth step as class of control languages for the (k + 1)st step. The language class obtained by thekth step is denoted by CTRL_k(). Denote by(S) the language class accepted by nondeterministic one-wayS automata, whereS is a storage type. We prove that for anyS, CTRL_k((S)) = (P _1t ^k (S)), whereP _1t ^k (S) is the storage type the configurations of which consist ofk-iterated one-turn pushdowns ofS-configurations. We establish a strong connection between iterated linear control and iterated one-turn pushdowns. In particular, we characterize CTRL _k ( _CF), where _CF is the class of context-free languages, by iterated one-turn pushdown automata in which the innermost pushdown is unrestricted.The work of the author has been supported by the Netherlands Organization for the advancement of pure research (Z.W.O.).     

Systems of Strings with High Mutual Complexity

Consider a binary string x ₀ of Kolmogorov complexity K(x ₀) n. The question is whether there exist two strings x ₁ and x ₂ such that the approximate equalities K(x _i x _j ) n and K(x _i x _j , x _k ) n hold for all 0 i, j, k 2, i j k, i k. We prove that the answer is positive if we require the equalities to hold up to an additive term O(log K(x ₀)). It becomes negative in the case of better accuracy, namely, O(log n).     

On characterizations of recursively enumerable languages

Summary Geffert has shown that earch recursively enumerable languageL over can be expressed in the formL{h(x) ^–1 g(x)x in ⁺} ^* where is an alphabet andg, h is a pair of morphisms. Our purpose is to give a simple proof for Geffert's result and then sharpen it into the form where both of the morphisms are nonerasing. In our method we modify constructions used in a representation of recursively enumerable languages in terms of equality sets and in a characterization of simple transducers in terms of morphisms. As direct consequences, we get the undecidability of the Post correspondence problem and various representations ofL. For instance,L =(L ₀) ^* whereL ₀ is a minimal linear language and is the Dyck reductiona, A.     

Constructing strongly convex hulls using exact or rounded arithmetic

One useful generalization of the convex hull of a setS ofn points is the -strongly convex -hull. It is defined to be a convex polygon with vertices taken fromS such that no point inS lies farther than outside and such that even if the vertices of are perturbed by as much as , remains convex. It was an open question as to whether an -strongly convexO()-hull existed for all positive . We give here anO(n logn) algorithm for constructing it (which thus proves its existence). This algorithm uses exact rational arithmetic. We also show how to construct an -strongly convexO( + )-hull inO(n logn) time using rounded arithmetic with rounding unit . This is the first rounded-arithmetic convex-hull algorithm which guarantees a convex output and which has error independent ofn.     

Sound and Complete Qualitative Simulation Needs “Quantitative” Filtering

The AI methodology of qualitative reasoning furnishes useful tools to scientists and engineers who need to deal with incomplete system knowledge during design, analysis, or diagnosis tasks. Qualitative simulators have a theoretical soundness guarantee; they cannot overlook any concrete equation implied by their input. On the other hand, the basic qualitative simulation algorithms have been shown to suffer from the incompleteness problem; they may allow non-solutions of the input equation to appear in their output. The question of whether a simulator with purely qualitative input which never predicts spurious behaviors can ever be achieved by adding new filters to the existing algorithm has remained unanswered. In this paper, we show that, if such a sound and complete simulator exists, it will have to be able to handle numerical distinctions with such a high precision that it must contain a component that would better be called a quantitative, rather than qualitative reasoner. This is due to the ability of the pure qualitative format to allow the exact representation of the members of a rich set of numbers.     

Sufficiency conditions for existence of an optimal feedback control in stochastic mechanics

In the framework of stochastic mechanics, the following problem is considered: in a set of admissible feedback controls v, with range inE ⁿ , find one minimizing the expectationE _sx { _s ^T L(t, (t), (t, (t)))dt + W _T ((T))} for all (s, x) [0,T) E ⁿ , whereL(t, x, ) = (/12)m ² – U(t, x) is the classical action integrand and is an-dimensional diffusion process in the weak sense, (see Bensoussan, 1982) with drift and diffusion coefficientD constant > 0.W _T andU are given real functions. Sufficiency conditions for the existence of such an optimal feedback control are given. Dedicated to George Leitmann Recommended by G.J. Olsder Presented at the Third Workshop on Control Mechanics in honor of George Leitmann, January 22–24, 1990, University of Southern California, Los Angeles, California (USA).     

Shallow circuits and concise formulae for multiple addition and multiplication

A theory is developed for the construction of carry-save networks with minimal delay, using a given collection of carry-save adders each of which may receive inputs and produce outputs using several different representation standards.The construction of some new carry-save adders is described. Using these carry-save adders optimally, as prescribed by the above theory, we get {, , }-circuits of depth 3.48 log₂ n and {, , }-circuits of depth 4.95 log₂ n for the carry-save addition ofn numbers of arbitrary length. As a consequence we get multiplication circuits of the same depth. These circuits put out two numbers whose sum is the result of the multiplication. If a single output number is required then the depth of the multiplication circuits increases respectively to 4.48 log₂ n and 5.95 log₂ n.We also get {, , }-formulae of sizeO (n ^3.13) and {, }-formulae of sizeO (n ^4.57) for all the output bits of a carry-save addition ofn numbers. As a consequence we get formulae of the same size for the majority function and many other symmetric Boolean functions.     

Specification and verification of database dynamics

Summary A framework is proposed for the structured specification and verification of database dynamics. In this framework, the conceptual model of a database is a many sorted first order linear tense theory whose proper axioms specify the update and the triggering behaviour of the database. The use of conceptual modelling approaches for structuring such a theory is analysed. Semantic primitives based on the notions of event and process are adopted for modelling the dynamic aspects. Events are used to model both atomic database operations and communication actions (input/output). Nonatomic operations to be performed on the database (transactions) are modelled by processes in terms of trigger/reaction patterns of behaviour. The correctness of the specification is verified by proving that the desired requirements on the evolution of the database are theorems of the conceptual model. Besides the traditional data integrity constraints, requirements of the form Under condition W, it is guaranteed that the database operation Z will be successfully performed are also considered. Such liveness requirements have been ignored in the database literature, although they are essential to a complete definition of the database dynamics.

Notation

Classical Logic Symbols (Appendix 1) for all (universal quantifier) - exists at least once (existential quantifier) - ¬ no (negation) - implies (implication) - is equivalent to (equivalence) - and (conjunction) - or (disjunction) Tense Logic Symbols (Appendix 1) G always in the future - G ₀ always in the future and now - F sometime in the future - F ₀ sometime in the future or now - H always in the past - H ₀ always in the past and now - P sometime in the past - P ₀ sometime in the past or now - X in the next moment - Y in the previous moment - L always - M sometime Event Specification Symbols (Sects. 3 and 4.1) (x) means immediately after the occurrence of x - (x) means immediately before the occurrence of x - (x) means x is enabled, i.e., x may occur next - { } ({w ₁} x{w ₂}) states that if w ₁ holds before the occurrence of x, then w ₂ will hold after the occurrence of x (change rule) - [ ] ([oa₁, ..., oa_n]x) states that only the object attributes oa₁, ..., oa _n are modifiable by x (scope rule) - {{ }} ({{w}}x) states that if x may occur next, then w holds (enabling rule) Process Specification Symbols (Sects. 5.3 and 5.4) :: for causal rules - for behavioural rules Transition-Pattern Composition Symbols (Sects. 5.2 and 5.3) ; sequential composition - ¦ choice composition - parallel composition - :| guarded alternative composition Location Predicates (Sect. 5.2) (z) means immediately after the occurrence of the last event of z (after) - (z) means immediately before the occurrence of the first event of z (before) - (z) means after the beginning of z and before the end of z (during) - ( z) means before the occurrence of an event of z (at)     

A forbidden subposet characterization of an order — dimension inequality

Dushnik and Miller defined the dimension of a partially ordered setX, DimX, as the minimum number of linear extensions ofX whose intersection is the partial ordering onX. The concept of dimension for a partially ordered set has applications to preference structures and the theory of measurement. Hiraguchi proved that DimX [|X|/2] when |X| 4. Bogart, Trotter, and Kimble gave a forbidden subposet characterization of Hiraguchi's inequality by constructing for eachn 2 the minimum collection _n of posets such that if [|X|/2] =n 2, then DimX < n unlessX contains one of the posets in _n . Recently Trotter gave a simple proof of Hiraguchi's inequality based on the following theorem. IfA is an antichain ofX and |X – A| =n 2, then DimX n. In this paper we give a forbidden subposet characterization of this last inequality.