Connected component and simple polygon intersection searching

Efficient data structures are given for the following two query problems: (i) preprocess a setP of simple polygons with a total ofn edges, so that all polygons ofP intersected by a query segment can be reported efficiently, and (ii) preprocess a setS ofn segments, so that the connected components of the arrangement ofS intersected by a query segment can be reported quickly. In these problems we do not want to return the polygons or connected components explicitly (i.e., we do not wish to report the segments defining the polygon, or the segments lying in the connected components). Instead, we assume that the polygons (or connected components) are labeled and we just want to report their labels. We present data structures of sizeO(n ¹⁺) that can answer a query in timeO(n ¹⁺+k), wherek is the output size. If the edges ofP (or the segments inS) are orthogonal, the query time can be improved toO(logn+k) usingO(n logn) space. We also present data structures that can maintain the connected components as we insert new segments. For arbitrary segments the amortized update and query time areO(n ^1/2+) andO(n ^1/2++k), respectively, and the space used by the data structure isO(n ¹⁺. If we allowO(n ^4/3+ space, the amortized update and query time can be improved toO(n ^1/3+ andO(n ^1/3++k, respectively. For orthogonal segments the amortized update and query time areO(log² n) andO(log² n+klogn), and the space used by the data structure isO (n logn). Some other related results are also mentioned.Part of this work was done while the second author was visiting the first author on a grant by the Dutch Organization for Scientific Research (N.W.O.). The research of the second author was also supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). The research of the first author was supported by National Science Foundation Grant CCR-91-06514.     

Proving total correctness of nondeterministic programs in infinitary logic

Summary It is shown how the weakest precondition approach to proving total correctness of nondeterministic programs can be formalized in infinitary logic. The weakest precondition technique is extended to hierarchically structured programs by adding a new primitive statement for operational abstraction, the nondeterministic assignment statement, to the guarded commands of Dijkstra. The infinitary logic L ₁ is shown to be strong enough to express the weakest preconditions for Dijkstra's guarded commands, but too weak for the extended guarded commands. Two possible solutions are considered: going to the essentially stronger infinitary logic L ₁₁ and restricting the power of the nondeterministic assignment statement in a way which allows the weakest preconditions to be expressed in L ₁.     

Iterated GSMs and Co-CFL

Summary We study the infinite words generated by an iterated gsm. The motivation was two fold. The first one was given by the apparent similarity between the iterated gsm and the iterated morphism. However contrary to the appearences almost all questions become undecidable. The second one was to disprove the following conjecture of Berstel: The language of coprefixes of an infinite word w is context free iff w is generated by an iterated gsm. We use for that the infinite word: w = abca² ba ² bca ⁴ ba ⁴ ba ² ba ⁴ bc ... (a ²ⁿ b)²ⁿ c .... We prove also that the degree of the ambiguity problem for coprefixes of iterated gsm is ₁-complete in the Kleene hierarchy. This result fills the gap between the degree of this problem for iterated morphisms which is ₀ and for arbitrary context-free grammars which is ₂-complete.This work has been supported by the Accion Integrada Hispano Francesa, 1987, 20/10     

Towards separating nondeterminism from determinism

The main result of this paper is a separation result: there is a positive integerk such that for all well-behaving functionst(n), there is a language accepted by a nondeterministic (multi-tape) Turing machine in timet(n) which cannot be accepting by any deterministic (multitape) Turing machine in timeO(t(n)) and simultaneously spaceo((t(n)) ^1/k ). This implies, for example that for any positive integer,l,l k, there is a language accepted by an ^l time bounded NDTM which cannot be accepted by a DTM in time and spaceO(n ^l ) andO((logn) ^l ) respectively for anyl. Such a result is not provable by direct diagonalization because we do not have time to simulate and do the opposite". We devise a different method for accomplishing the result: We first use an alternating Turing machine to speed up the simulation of a time and space bounded DTM and then argue that if our separation result did not hold, every NDTM can itself be simulated faster by another NDTM producing a contradiction to the standard hierarchy results. Some other applications of this method are also presented.Supported by NSF Grant No. MCS-8105557     

Optimization and experimental investigations of stiffened, axially compressed CFRP-panels

Thin-walled, unstiffened and stiffened shell structures made of fibre composite materials are frequently applied due to their high stiffness/strength to weight ratios in all fields of lightweight constructions. One major design criterion of these structures is their sensitivity with respect to buckling failure when subjected to inplane compression and shear loads. This paper describes how the structural analysis program BEOS (Buckling of Eccentrically Orthotropic Sandwich shells) is combined with the optimization procedure SAPOP (Structural Analysis Program and Optimization Procedure) to produce a tool for designing optimum CFRP-panels against buckling. Experimental investigations are used to justify the described procedures.Nomenclature C, C _b material stiffness matrices (shell, beam stiffener) - f objective function - F _cr buckling load - g vector of inequality constraints - K,K _g , stiffness matrix, geometrical stiffness matrix, condensed stiffness matrix - n _s ,n _b vector of stress resultants (shell, beam stiffener) - N _x ,N _y ,N _xy membrane forces of the shell - P _x ,P _y ,P _xy membrane forces of the stiffener - r _x ,r _y ,r _xy radii of curvature - ⁿ n-dimensional Euclidean space - W strain energy - u, v, w deformations inx, y, z direction - x, y, z global coordinate system - x vector of design variables - y, z right-hand side, left-hand side eigenvector - variational symbol - _i ^k Kronecker's delta - e _s ,e _b strain vectors (shell, beam stiffener) - , _cr load factor, buckling load factor - , e total energy, external potential energy A (^) sign above a variable points out that this variable belongs to the prebuckling state.     

The Complexity of Modellability in Finite and Computable Signatures of a Constraint Logic for Head-Driven Phrase Structure Grammar

The SRL (speciate re-entrant logic) of King (1989) is a sound, complete and decidable logic designed specifically to support formalisms for the HPSG (head-driven phrase structure grammar) of Pollard and Sag (1994). The SRL notion of modellability in a signature is particularly important for HPSG, and the present paper modifies an elegant method due to Blackburn and Spaan (1993) in order to prove that

Relativized polynomial hierarchies extending two levels

The existence of relativized polynomial hierarchies extending exactly two levels is shown. More precisely, oraclesX andY are constructed such thatNP(X) ₂ ^{P, X} = ₂ ^{P, X} and ₂ ^{P, Y} ₂ ^{P, Y} = ₂ ^{P, Y} . These results answer a question posed by Baker, Gill, and Solovay ([1]) and generalize their constructions of relativized polynomial hierarchies extending 0 resp. 1 level; i.e.,P(A) = NP(A) resp.P(B) NP(B) = coNP(B) for recursive oraclesA andB.     

A note to the definition of the ŁΠ-algebras

The -algebras are interesting algebraic structures. They were introduced by Esteva, Godo, and Montagna. These algebras are closely related to the well-known MV-algebras and -algebras. They have two sets of operations and reduct to one set is an MV-algebra and to the other one is a -algebra.Other important reducts of -algebras are so-called P-algebras (an MV-algebras enriched with product connective) and -algebras (-algebras with additional involutive negation).The definition of -algebras is based on its MV-algabraic reduct and the additional identities. In this paper we present how to base this definition on the other reducts we mention above. We present minimal sets of conditions which has to be added to the defining conditions of those reducts in order to obtain -algebras.     

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.     

Generalization of a Suffix Tree for RNA Structural Pattern Matching

In molecular biology, it is said that two biological sequences tend to have similar properties if they have similar three-dimensional structures. Hence, it is very important to find not only similar sequences in the string sense, but also structurally similar sequences from databases. In this paper we propose a new data structure that is a generalization of a parameterized suffix tree (p-suffix tree for short) introduced by Baker. We call it the structural suffix tree or s-suffix tree for short. The s-suffix tree can be used for finding structurally related patterns of RNA or single-stranded DNA. Furthermore, we propose an O(n(log|| + log||)) on-line algorithm for constructing it, where n is the sequence length, || is the size of the normal alphabet, and || is that of the alphabet called parameter, which is related to the structure of the sequence. Our algorithm achieves linear time when it is used to analyze RNA and DNA sequences. Furthermore, as an algorithm for constructing the p-suffix tree, it is the first on-line algorithm, though the computing bound of our algorithm is the same as that of Kosarajus best-known algorithm. The results of computational experiments using actual RNA and DNA sequences are also given to demonstrate our algorithms practicality.     

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.     

Binary Codes Formed by Functions with Nontrivial Inertia Groups

Let K be a permutation group acting on binary vectors of length n and F _K be a code of length 2 ⁿ consisting of all binary functions with nontrivial inertia group in K. We obtain upper and lower bounds on the covering radii of F _K , where K are certain subgroups of the affine permutation group GA _n . We also obtain estimates for distances between F _K and almost all functions in n variables as n . We prove the existence of functions with the trivial inertia group in GA _n for all n 7. An upper bound for the asymmetry of a k-uniform hypergraph is obtained.     

Computational geometry algorithms for the systolic screen

Adigitized plane of sizeM is a rectangular M × M array of integer lattice points called pixels. A M × M mesh-of-processors in which each processorP _ij represents pixel (i,j) is a natural architecture to store and manipulate images in ; such a parallel architecture is called asystolic screen. In this paper we consider a variety of computational-geometry problems on images in a digitized plane, and present optimal algorithms for solving these problems on a systolic screen. In particular, we presentO(M)-time algorithms for determining all contours of an image; constructing all rectilinear convex hulls of an image (peeling); solving the parallel and perspective visibility problem forn disjoint digitized images; and constructing the Voronoi diagram ofn planar objects represented by disjoint images, for a large class of object types (e.g., points, line segments, circles, ellipses, and polygons of constant size) and distance functions (e.g., allL _p metrics). These algorithms implyO(M)-time solutions to a number of other geometric problems: e.g., rectangular visibility, separability, detection of pseudo-star-shapedness, and optical clustering. One of the proposed techniques also leads to a new parallel algorithm for determining all longest common subsequences of two words.Research supported by the Naural Sciences and Engineering Research Council of Canada. With the Editor-in-Chief's permission, this paper was sent to the referees in a form which kept them unaware of the fact that the Guest Editor is one of the co-authors.     

A New Implementation of Automath

This paper presents aut, a modern Automath checker. It is a straightforward re-implementation of the Zandleven Automath checker from the seventies. It was implemented about five years ago, in the programming language C. It accepts both the AUT-68 and AUT-QE dialects of Automath. This program was written to restore a damaged version of Jutting's translation of Landau's Grundlagen. Some notable features: It is fast. On a 1 GHz machine it will check the full Jutting formalization (736 K of nonwhitespace Automath source) in 0.6 seconds. Its implementation of -terms does not use named variables or de Bruijn indices (the two common approaches) but instead uses a graph representation. In this representation variables are represented by pointers to a binder. The program can compile an Automath text into one big Automath single line-style -term. It outputs such a term using de Bruijn indices. (These -terms cannot be checked by modern systems like Coq or Agda, because the -typed -calculi of de Bruijn are different from the -typed -calculi of modern type theory.)The source of aut is freely available on the Web at the address .     

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.     

Size of the Largest Antichain in a Partition Poset

Partitions {(k ₁,..., k )} of a given set are considered as a partially ordered set (poset) with a natural partial ordering with respect to inclusion. Asymptotics for the size of the largest antichain in this poset is found for fixed.     

Undirecteds-t connectivity in polynomial time and sublinear space

Thes-t connectivity problem for undirected graphs is to decide whether two designated vertices,s andt, are in the same connected component. This paper presents the first known deterministic algorithms solving undirecteds-t connectivity using sublinear space and polynomial time. Our algorithms provide a nearly smooth time-space tradeoff between depth-first search and Savitch's algorithm. Forn vertex,m edge graphs, the simplest of our algorithms uses spaceO(s),n ^1/2log₂ nsnlog₂ n, and timeO(((m+n)n ² log² n)/s). We give a variant of this method that is faster at the higher end of the space spectrum. For example, with space (nlogn), its time bound isO((m+n)logn), close to the optimal time for the problem. Another generalization uses less space, but more time: spaceO(n ^1/logn), for 2log₂ n, and timen ^O(). For constant the time remains polynomial.     

Approximate motion planning and the complexity of the boundary of the union of simple geometric figures

We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have a running time of (n ²), wheren is the number of obstacle corners. We introduce thetightness of a motion-planning problem as a measure of the difficulty of a planning problem in an intuitive sense and describe an algorithm with a running time ofO((a/b · 1/_crit + 1)n(logn)²), wherea b are the lengths of the sides of a rectangle and _crit is the tightness of the problem. We show further that the complexity (= number of vertices) of the boundary ofn bow ties (see Figure 1) isO(n). Similar results for the union of other simple geometric figures such as triangles and wedges are also presented.This work was supported partially by the DFG Schwerpunkt Datenstrukturen und Algorithmen, Grants Me 620/6 and Al 253/1, and by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM).     

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.