Splitting a configuration in a simplex

This paper presents a new method of partition, named-splitting, of a point set ind-dimensional space. Given a pointG in ad-dimensional simplexT, T(G;i) is the subsimplex spanned by G and the ith facet ofT. LetS be a set ofn points inT, and let be a sequence of nonnegative integers ₁, ..., n_d+1 satisfying _i=1 ^d+1 ₁=n The-splitter of (T, S) is a pointG inT such thatT(G;i) contains at least _i points ofS in its closure for everyi=1, 2, ...,d + 1. The associated dissection is the re-splitting.The existence of a-splitting is shown for any (T, S) and, and two efficient algorithms for finding such a splitting are given. One runs inO(d²n logn + d³n) time, and the other runs inO(n) time if the dimensiond can be considered as a constant. Applications of re-splitting to mesh generation, polygonal-tour generation, and a combinatorial assignment problem are given.     

Stabilizability of linear systems defined overC *-algebras

LetF andG be elements of aC ^*-algebraA. Assume that, for each irreducible^*-representation ofA on a Hilbert space210B; , there is a bounded linear operatorL B( ) such that the spectrum of(F) –(G)L is contained in the open left half plane. We prove that there is then an elementL A such that the spectrum ofF — GL is contained in the open left half plane. That is, if the system (F, G) is locally stabilizable, then it is stabilizable. We also consider the analogous problem with the open left half plane replaced by the open unit disk.This paper was supported in part by the National Science Foundation under Grant NSF-MCS-8002138.     

Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity

We investigate three-dimensional visibility problems for scenes that consist ofn non-intersecting spheres. The viewing point moves on a flightpath that is part of a circle at infinity given by a planeP and a range of angles {(t)¦t[01]} [02]. At timet, the lines of sight are parallel to the ray inP, which starts in the origin ofP and represents the angle(t) (orthographic views of the scene). We give an algorithm that computes the visibility graph at the start of the flight, all time parameters at which the topology of the scene changes, and the corresponding topology changes. The algorithm has running time0(n + k + p) logn), wheren is the number of spheres in the scene;p is the number of transparent topology changes (the number of different scene topologies visible along the flight path, assuming that all spheres are transparent); andk denotes the number of vertices (conflicts) which are in the (transparent) visibility graph at the start and do not disappear during the flight.The second author was supported by the ESPRIT II Basic Research Actions Program, under Contract No. 3075 (project ALCOM).     

PI k mass production and an optimal circuit for the Nečiporuk slice

Letf: {0,1} ⁿ {0,1} ^m be anm-output Boolean function inn variables.f is called ak-slice iff(x) equals the all-zero vector for allx with Hamming weight less thank andf(x) equals the all-one vector for allx with Hamming weight more thank. Wegener showed that PI _k -set circuits (set circuits over prime implicants of lengthk) are at the heart of any optimum Boolean circuit for ak-slicef. We prove that, in PI _k -set circuits, savings are possible for the mass production of anyFX, i.e., any collectionF ofm output-sets given any collectionX ofn input-sets, if their PI _k -set complexity satisfiesSC _m (FX)3n+2m. This PI _k mass production, which can be used in monotone circuits for slice functions, is then exploited in different ways to obtain a monotone circuit of complexity 3n+o(n) for the Neiporuk slice, thus disproving a conjecture by Wegener that this slice has monotone complexity (n ^3/2). Finally, the new circuit for the Neiporuk slice is proven to be asymptotically optimal, not only with respect to monotone complexity, but also with respect to combinational complexity.     

Using Metric Spaces in Optimum Scheduling

The solution of an optimum problem of scheduling with n workpieces and m machine tools represents an optimum schedule of putting pieces on machines. In turn, the schedule is defined by an optimum collection of m permutations out of n objects, i.e., the vector permutation = (₁, ..., _m ), where each permutation _i (1 i m) points up the sequence of working of all pieces on the ith machine. In this case, to each admissible schedule there must correspond an integral point from the m-dimensional Euclidean space of permutations (or, which is practically the same, the permutation out of numbers {1, 2, ..., mn}. In an effort to seek an optimum schedule, use is made of the notion of a metric space in the set of admissible schedules and the justified methodology of the search for an optimum schedule. A few metric spaces are described and analyzed and their comparative effectiveness is investigated for the solution of a different-route problem of scheduling.     

On the group of automorphisms of strongly connected automata

LetA = (S, I, M) be a strongly connected finite automaton withn states. Weeg has shown that ifA has a group of automorphisms of orderm, then there is a partition of the setS inton/m blocks each withm states. Furthermore ifs _i ands _j are in the same block of, thenT _ii =T _jj , whereT _ii = {x|x ^* and thenM(s _i , x) =s _i }. It will be shown that the partition also must have the substitution property and that these two conditions are sufficient for ann state strongly connected automaton to have a group of automorphisms of orderm.Necessary and sufficient conditions for twon-state strongly connected automata to have isomorphic automorphism groups are given. Also, it is demonstrated that forT _ii to equalT _jj it is necessary to check only a finite number of tapes and consequently provide an algorithm for determining whether or notA has a group of automorphisms of orderm. This research was partially supported by the National Science Foundation under Grant No. G.P. 7077.     

A Solution for the N-bit Parity Problem Using a Single Translated Multiplicative Neuron

A solution to the N-bit parity problem employing a single multiplicative neuron model, called translated multiplicative neuron ( _t -neuron), is proposed. The _t -neuron presents the following advantages: (a) N1, only 1 _t -neuron is necessary, with a threshold activation function and parameters defined within a specific interval; (b) no learning procedures are required; and (c) the computational cost is the same as the one associated with a simple McCulloch-Pitts neuron. Therefore, the _t -neuron solution to the N-bit parity problem has the lowest computational cost among the neural solutions presented to date.     

Rangierkomplexität von permutationen

Summary We define a measure of complexity for (the group of permutations ofn elements). We thus obtain non trivial lower bounds for the number of Turing steps necessary for applaying a permutation to a tape withn entries. Transposing annxn matrix, for example, stored linearly needs at leastCn ² Ign steps.     

The lexicographically first maximal subgraph problems:P-completeness andNC algorithms

The lexicographically first maximal (lfm) subgraph problem for a property is to compute the lfm vertex set whose induced subgraph satisfies . The main contribution of this paper is theP-completeness of the lfm subgraph problem for any nontrivial hereditary property. We also observe that most of the lfm subgraph problems are stillP-complete even if the instances are restricted to graphs with degree 3. However, some exceptions are found. For example, it is shown that the lfm 4-cycle free subgraph problem is inNC ² for graphs with degree 3 but turns out to beP-complete for graphs with degree 4. Further, we analyze the complexity of the lfmedge-induced subgraph problem for some graph properties and show that it has a different complexity feature.This work was done while the author visited Universität-GH-Paderborn and a part of this paper was presented at the 14th ICALP, Karlsruhe, 1987.     

Randomized vs. deterministic decision tree complexity for read-once Boolean functions

We consider the deterministic and the randomized decision tree complexities for Boolean functions, denotedDC(f) andRC(f), respectively. A major open problem is how smallRC(f) can be with respect toDC(f). It is well known thatRC(f)DC(f) ^0.5 for every Boolean functionf (called 0.5-exponent). On the other hand, some Boolean functionf is known to haveRC(f) = (DC(f))^0.753...) (or 0.753...-exponent). It is not known whether there is a Boolean function with exponent smaller than 0.753... Likewise, no lower bound for arbitrary Boolean functions with exponent greater than 0.5 is known.Our result is a 0.51 lower bound on the exponent for everyread-once function. Read-once means that each input variable appears exactly once in the Boolean formula representing the function. To obtain this result we generalize an existing lower bound technique and combine it with restriction arguments. This result provides a lower bound ofn ^0.51 on the number of positions that have to be evaluated by any randomized - pruning algorithm computing the value of any two-person zero-sum game tree withn final positions.     

Constructing sets of functions which have a givenF-cardinality

The termF-cardinality of (=F-card()) is introduced whereF: ^{n n} is a partial function and is a set of partial functionsf: ^{n n} . TheF-cardinality yields a lower bound for the worst-case complexity of computingF if only functionsf can be evaluated by the underlying abstract automaton without conditional jumps. This complexity bound isindependent from the oracles available for the abstract machine. Thus it is shown that any automaton which can only apply the four basic arithmetic operations needs (n logn) worst-case time to sortn numbers; this result is even true if conditional jumps witharbitrary conditions are possible. The main result of this paper is the following: Given a total functionF: ^{n n} and a natural numberk, it is almost always possible to construct a set such that itsF-cardinality has the valuek; in addition, can be required to be closed under composition of functionsf,g . Moreover, ifF is continuous, then consists of continuous functions.     

There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees

Let S be a set ofn points in the plane. For an arbitrary positive rationalr, we construct a planar straight-line graph onS that approximates the complete Euclidean graph onS within the factor (1 + 1/r)[2/3 cos(/6)], and it has length bounded by 2r + 1 times the length of a minimum Euclidean spanning tree onS. Given the Deiaunay triangulation ofS, the graph can be constructed in linear time.     

A universal topological transformation group inL 2 (G × G)

LetG denote an infinite,-compact, locally compact topological group. In this paper a construction is given for a topological transformation groupH _G with the Hilbert spaceL ² (G × G) as a phase space such that any topological transformation group (G, X, ) can be embedded inH _G , providedX is a separable metrizable space and is a bounded action. The class of such topological transformation groups contains all actions ofG on separable, metrizable, locally compact spaces.     

Size-depth tradeoff in monotone Boolean formulae

Summary Formula size and depth are two important complexity measures of Boolean functions. We study the tradeoff between those two measures: We give an infinite set of Boolean functions and show for nearly each of them: There is no monotone formula computing it optimal with respect to both measures. We give a lower and upper bound on the product of size and depth of monotone formulae computing our functions. That implies, moreover, a logarithmic lower bound on circuit depth.Denotations the set of natural numbers {1,2,...} - for x>0, x =max{y{0}¦y¦<=x} - log logarithm to the base 2     

A priori Probability That Two Qubits Are Unentangled

In a previous study (P. B. Slater, Eur. Phys. J. B. 17, 471 (2000)), several remarkably simple exact results were found, in certain specialized m-dimensional scenarios (m 4), for the a priori probability that a pair of qubits is unentangled/separable. The measure used was the volume element of the Bures metric (identically one-fourth the statistical distinguishability [SD] metric). Here, making use of a newly-developed (Euler angle) parameterization of the 4 × 4 density matrices of Tilma, Byrd and Sudarshan, we extend the analysis to the complete 15-dimensional convex set (C) of arbitrarily paired qubits—the total SD volume of which is known to be ⁸ / 1680 = ⁸/2⁴ 3 5 7 5.64794. Using advanced quasi-Monte Carlo procedures (scrambled Halton sequences) for numerical integration in this high-dimensional space, we approximately (5.64851) reproduce that value, while obtaining an estimate of 0.416302 for the SD volume of separable states. We conjecture that this is but an approximation to ⁶/2310 = ⁶ / (2 3 5 7 11) 0.416186. The ratio of the two volumes, 8/11²2 .0736881, would then constitute the exact Bures/SD probability of separability. The SD area of the 14-dimensional boundary of C is 142⁷/12285 = 2 71⁷/3³ 5 7 13 34.911, while we obtain a numerical estimate of 1.75414 for the SD area of the boundary of separable states. PACS: 03.67.-; 03.65.Ud; 02.60.Jh; 02.40.Ky     

An improved complexity hierarchy on the depth of Boolean functions

Summary Circuit depth is an important complexity measure for a Boolean function. Let some Boolean function of n variables have depth k according to an arbitrary binary basis . For each j where [log n]jk we prove the existence of a Boolean function f with the following properties. f depends essentially on n variables and the depth of f according to is exactly j Thus we state the best possible hierarchy result on the depth of all nondegenerate Boolean functions.     

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.     

A logical encoding of the π-calculus: model checking mobile processes using tabled resolution

We present MMC, a model checker for mobile systems specified in the style of the -calculus. MMCs development builds on that of XMC, a model checker for an expressive extension of Milners value-passing calculus implemented using the XSB tabled logic-programming engine. MMC addresses the salient issues that arise in the -calculus, including scope extrusion and intrusion and dynamic generation of new names to avoid name capture. We show that logic programming provides an efficient implementation platform for model checking -calculus specifications and can be used to obtain an exact encoding of the -calculuss transitional semantics. Moreover, MMC is easily extended to handle process expressions in the spi-calculus of Abadi and Gordon. Our experimental data show that MMC outperforms other known tools for model checking the -calculus.     

Learning reliably and with one-sided error

Reliable and probably useful learning, proposed by Rivest and Sloan, is a variant of probably approximately correct learning. In this model the hypothesis must never misclassify an instance but is allowed to answer I don't know with a low probability. We derive upper and lower bounds for the sample complexity of reliable and probably useful learning in terms of the combinatorial characteristics of the concept class to be learned. This is done by reducing reliable and probably useful learning to learning with one-sided error. The bounds also hold for a slightly weaker model that allows the learner to output with a low probability a hypothesis that makes misclassifications. We see that in these models learning with one oracle is more difficult than learning with two oracles. Our results imply that monotone Boolean conjunctions or disjunctions cannot be learned reliably and probably usefully from a polynomial number of examples. Rectangles in ⁿ forn 2 cannot be learned from any finite number of examples.A preliminary version of this paper appeared under the title Reliable and useful learning inProceedings of the 2nd Annual Workshop on Computational Learning Theory, Morgan Kaufmann, San Mateo, CA, 1989, pp. 365–380. This work was supported by the Academy of Finland.     

Priority as extremal probability

We extend the stratified model of probabilistic processes to obtain a very general notion ofprocess priority. The main idea is to allow probability guards of value 0 to be associated with alternatives of a probabilistic summation expression. Such alternatives can be chosen only if the non-zero alternatives are precluded by contextual constraints. We refer to this model as one of extremal probability and to its signature asPCCS . We providePCCS with a structural operational semantics and a notionof probabilistic bisimulation, which is shown to be a congruence. Of particular interest is the abstractionPCCS ofPCCS in which all non-zero probability guards are identified.PCCS represents a customized framework for reasoning about priority, and covers all features of process algebras proposed for reasoning about priority that we know of.A preliminary version of this paper appeared inProceedings of CONCUR '90 — First International Conference on Concurrency Theory, Vol. 458 of the Springer-Verlag seriesLecture Notes in Computer Science, pp. 456–466, Aug. 1990. The research of Scott Smolka was supported in part by NSF Grants CCR-9120995, CCR-9208585 and CCR-9505562; and AFOSR Grants F49620-93-1-0250, F49620-95-1-0508 and F49620-96-1-0087.