One step integration methods of third-fourth order accuracy with large hyperbolic stability limits

One step integration methods of third and fourth order accuracy that use K function evaluations to solve the system of differential equations $\text{d}\text{y}\text{d}\text{t}\text{= A · y}$ are proposed. These methods are shown to have a hyperbolic stability limit of y (K ? 1)² ? 1 which approaches the theoretical maximum limit of K ? 1 at large K obtained for methods of lower order accuracy.     

On time versus space II

Every t(n)-time bounded RAM (assuming the logarithmic cost measure) can be simulated by a t(n)/log t(n)-space bounded Turing machine and every t(n)-time bounded Turing machine with d-dimensional tapes by a bounded machine, where n is the length of the input. A class $\text{E}$ of storage structures which generalizes multidimensional tapes is defined. Every t(n)-time bounded Turing machine whose storage structures are in $\text{E}$ can be simulated by a t(n) loglog t(n)/log t(n)-space bounded Turing machine.     

A simple linear-time algorithm for in situ merging

It is generally believed that the time-cost of solving any size n problem using two-way divide-and-conquer is minimized by balancing—that is, by dividing the problem into subproblems of size $\text{?}\text{n}\text{2}\text{?}$ and $\text{?}\text{n}\text{2}\text{?}$. A counter-example is presented: balanced division, applied to finding the greatest and least elements of a size n set, will in the worst case force 11% more comparisons to be made than an optimal division such as into subsets of sizes 2 and n?2. A necessary condition and a slightly stronger sufficient condition are given for balancing to be cost-optimal. Even if balancing is cost-optimal, it may not be the only cost-optimal division strategy; a necessary and sufficient condition is given for a division strategy to be ‘balanced enough’ to be cost-optimal. As an application, a new iterative merge-sorting algorithm is presented which requires no more comparisons than the balanced one of Erkio and Peltola (1977) but merges subarrays consisting of consecutive elements of the whole array.     

The complexity of incremental convex hull algorithms in Rd

The complexity of any incremental convex hull algorithm in R^d is shown to be $\text{Ω(n}{}^{\mathrm{<mtext>[</mtext><mtext>(d+1)</mtext><mtext>2</mtext><mtext>]</mtext>}}\text{)}$ for n points and constant d.     

Simulations among multidimensional turing machines

For all d ? 1 and all e >d, every deterministic multihead e-dimensional Turing machine of time complexity T(n) can be simulated on-line by a deterministic multihead d-dimensional Turing machine in time O(T(n)^1+1?d?1?(logT(n))⁰⁽¹⁾). This simulation almost achieves the known lower bound $\text{Ω(T(n)}{}^{\mathrm{1+1?}}\text{d?1?e)}$ on the time required. The simulation is interpreted in terms of dynamic embeddings among arrays with local access.     

A note on ‘geometric transforms’ of digital sets

We define a ‘geometric transform’ on the digital plane as a function ? that takes pairs (P, S), where S is a set and P a point of S, into nonnegative integers, and where $\text{?(S, P)}$ depends only on the positions of the points of S relative to P. Transforms of this type are useful for segmenting and describing S. Two examples are ‘distance transforms’, for which $\text{?(S, P)}$ is the distance from P to S, and ‘isovist transforms’, where $\text{?(S, P)}$, is the area of the part S visible from P. This note characterizes geometric transforms that have certain simple set-theoretic properties, e.g., such that $\text{?(S?T,P) = ?(S,P)∧?(T,P)}$ for all S, T, P. It is shown that a geometric transform has this intersection property if and only if it is defined in a special way in terms of a ‘neighborhood base’; the class of such ‘neighborhood transforms’ is a generalization of the class of distance transforms.     

Ray shooting on triangles in 3-space

We present a uniform approach to problems involving lines in 3-space. This approach is based on mapping lines inR ³ into points and hyperplanes in five-dimensional projective space (Plücker space). We obtain new results on the following problems:

1. Preprocessn triangles so as to answer efficiently the query: “Given a ray, which is the first triangle hit?” (Ray- shooting problem). We discuss the ray-shooting problem for both disjoint and nondisjoint triangles.
2. Construct the intersection of two nonconvex polyhedra in an output sensitive way with asubquadratic overhead term.
3. Construct the arrangement ofn intersecting triangles in 3-space in an output-sensitive way, with asubquadratic overhead term.
4. Efficiently detect the first face hit by any ray in a set of axis-oriented polyhedra.
5. Preprocessn lines (segments) so as to answer efficiently the query “Given two lines, is it possible to move one into the other without crossing any of the initial lines (segments)?” (Isotopy problem). If the movement is possible produce an explicit representation of it.

     

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 form equivalence of L-forms

In [5] the notion of an L form F defining a family $\text{L}$_d(F) of languages by means of X-interpretations has been introduced. Here X is one of a number of possible variations of the notion of interpretation originally used in [1] for grammar forms. In this paper it is shown that the questions whether $\text{L}{}_{\mathrm{d}}\text{(F) =}\text{L}{}_{\mathrm{d}}\text{(F}{}_1\text{)}$ for L forms F and F₁ is decidable, if deterministic interpretations of PDOL systems are considered, where L(F) and L(F₁) contain at most one word of length n for any n ? 0, and it is shown that same question is undecidable, if full or uniform interpretations are chosen. In contrast to this, no such results are known for grammar forms at this point.     

The time-precision tradeoff problem on on-line probabilistic Turing machines

A probabilistic Turing machine (PTM) is a Turing machine that flips an unbiased coin to decide its next movement and solves a problem with some error probability. It is expected that PTMs need more time if a smaller error probability is required. This is a sort of time-precision tradeoff and is shown to occur actually on on-line probabilistic Turing machine acceptors (ONPTMs). That is, we show the existence of a set such that it is recognized by an ONPTM with $\text{1}\text{2}\text{-(}\text{log}\text{n)/}\text{8}\text{n}$ bounded error probability in O(n) time but for every $\text{ε, 0<ε<}\text{1}\text{2}$, it requires more than O((n/log n)²) time to recognize this set with bounded error probability by ONPTMs. Moreover our result is also shown to be an example of difference between nondeterministic computations and probabilistic ones.     

Some polynomials that are hard to compute

Using the result of Heintz and Sieveking [1], we show that the polynomials $\text{Σ}{}_{\mathrm{1?j?d}}\text{b}{}^{\mathrm{<mtext>1</mtext><mtext>i</mtext>}}\text{X}{}^{\mathrm{j}}$ with b positive real different from one, and Σ_1?j?dj^rX^j with r rational not integer, are hard to compute.     

Circuit size is nonlinear in depth

Two fundamental complexity measures for a Boolean function f are its circuit depth d(f) and its circuit size c(f). It is shown that $\text{c?}\text{1}\text{4}\text{d·}\text{log}{}_2\text{d}$ for all f.     

Remarks on blind and partially blind one-way multicounter machines

We consider one-way nondeterministic machines which have counters allowed to hold positive or negative integers and which accept by final state with all counters zero. Such machines are called blind if their action depends on state and input alone and not on the counter configuration. They are partially blind if they block when any counter is negative (i.e., only nonnegative counter contents are permissible) but do not know whether or not any of the counters contain zero. Blind multicounter machines are equivalent in power to the reversal bounded multicounter machines of Baker and Book [1], and for both blind and reversal bounded multicounter machines, the quasirealtime family is as powerful as the full family. The family of languages accepted by blind multicounter machines is the least intersection closed semiAFL containing {aⁿbⁿ|n?0} and also the least intersection closed semiAFL containing the two-sided Dyck set on one letter. Blind multicounter machines are strictly less powerful than quasirealtime partially blind multicounter machines. Quasirealtime partially blind multicounter machines accept the family of computation state sequences or Petri net languages which is equal to the least intersection closed semiAFL containing the one-sided Dyck set on one letter but is not a principal semiAFL. For partially blind multicounter machines, as opposed to blind machines, linear time is more powerful than quasirealtime. Assuming that the reachability problem for vector addition systems is decidable [16], partially blind multicounter machines accept only recursive sets and do not accept even $\text{{a}{}^{\mathrm{n}}\text{b}{}^{\mathrm{n}}\text{|n?0}{}^1$, and quasirealtime partially blind multicounter machines are less powerful than general quasirealtime multicounter machines.     

Complete problems for deterministic polynomial time

Log space reducibility allows a meaningful study of complexity and completeness for the class $\text{P}$ of problems solvable in polynomial time (as a function of problem size). If any one complete problem for $\text{P}$ is recognizable in log^k(n) space (for a fixed k), or requires at least n^c space (where c depends upon the program), then all complete problems in $\text{P}$ have the same property. A variety of familiar problems are shown complete for $\text{P}$, including context-free emptiness, infiniteness and membership, establishing inconsistency of propositional formulas by unit resolution, deciding whether a player in a two-person game has a winning strategy, and determining whether an element is generated from a set by a binary operation.     

On recognizing graph properties from adjacency matrices

A conjecture of Aanderaa and Rosenberg [15] motivates this work. We investigate the maximum number C(P) of arguments of P that must be tested in order to compute P, a Boolean function of d Boolean arguments. We present evidence for the general conjecture that C(P) = d whenever P(0^d) ≠ P(1^d) and P is invariant under a transitive permutation group acting on the arguments. A non-constructive argument (not based on the construction of an “oracle”) settles this question for d a prime power. We use this result to prove the Aanderaa-Rosenberg conjecture: at least $\text{v}{}^2\text{16}$ entries of the adjacency matrix of a v-vertex undirected graph G must be examined in the worst case to determine if G has any given non-trivial monotone graph property.     

Entropy and set covering

If the set covering constraints are Ax ? 1 and x_j ∈ {0,1}, the prior probability that the jth subset participates in an optimal covering (independently of subset costs) is shown to be given by the principal row eigenvector of A¹A, where $\text{a}{}_{\mathrm{ji}}{}^1\text{= 1 ? a}{}_{\mathrm{ij}}$. These probabilities lead to new and interesting objective functions, which are shown to be equivalent to cross entropy or weighted cross-entropy. The probabilities can also be used to obtain better bounds for heuristic solutions to optimal covering and set representation problems.     

An optimal triangulation for second-order elliptic problems

Let Ω be a polygonal domain in $\text{R}{}^{\mathrm{n}}$, τ_h an associated triangulation and u_h the finite element solution of a well-posed second-order elliptic problem on (Ω, τ_h). Let M = {M_i}^{p + q}_{i = 1} be the set of nodes which defines the vertices of the triangulation τ_h: for each i,$\text{M}{}_{\mathrm{i}}\text{= {x}{}_{\mathrm{i}}{}^{\mathrm{l}}\text{¦1 ? l ?n}}$ in Rⁿ. The object of this paper is to provide a computational tool to approximate the best set of positions M? of the nodes and hence the best triangulation $\text{}\text{?}\text{gt}{}_{\mathrm{h}}$ which minimizes the solution error in the natural norm associated with the problem.The main result of this paper are theorems which provide explicit expressions for the partial derivatives of the associated energy functional with respect to the coordinates x_i^l, 1 ? l ? n, of each of the variable nodes M_i, i = 1,…, p.     

Pattern recognition: The categorical setting

We present in this paper the categorical setting for patterns and pattern recognition, bringing together several of our previous results and unifying the algebraic syntactic-oriented, automata-theoretical, and topological formalisms. After briefly recalling these formalisms and terminology, we first show under which conditions images $\text{I}{}_{\mathrm{\mu }}\text{?}\text{I}$ and deformations δ?Δ can be organized in a category $\text{(}\text{I}\text{,Δ) =}\text{I}{}^{\mathrm{\Delta }}$, and how one can associate with it a recognition category $\text{(}\text{I}\text{,Γ) =}\text{I}$, where Γ is a group of similarities γ?Γ included in Δ. Probes and recognition functions are characterized as being invariant functors of categories, and a particular class of probes—projections—is studied using the notion of retract of a category; this notion is then used to characterize the family ? of patterns. The relationship between $\text{I}$, $\text{I}$^Δ, and ? is described. Further investigation of recognition in $\text{I}$ is performed by exhibiting the practical meaning of retracts along with their lifting properties. Furthermore, the recognition problem associated with the initial deformed image category $\text{I}$^Δ is studied, introducing the skeleton Σ of $\text{I}$^Δ; the role played by retracts is again emphasized. Finally we present the connection between patterns, projections and, skeletons; the link existing between the present formalism and current application; and the topological explanation of the “useful” properties of projections and skeletons. The paper ends by listing some open research problems.     

A probabilistic algorithm for vertex connectivity of graphs

A probabilistic algorithm is presented which computes the vertex connectivity of an undirected graph G = (V,E) in expected time $\text{O((-log ε|V|}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}\text{|E|)}$ with error probability at most e provided that |E|<frcase|1/2d|V|² for some universal constant d<1.