In this paper we present a theoretical basis justifying the incorporation of decidability results for a first-order theory T into an automated theorem prover for T. We state rules which extend resolution using decidability results relative to T in both the ground and the non-ground case, and prove the correctness and completeness of these rules. This is done by considering the ground case of such theories first, and then by applying a straightforward lifting argument. Examples are given illustrating the inference speed-ups which can be obtained by considering decision procedures with resolution-based inference.

We analyse the combinatorial complexity κ(F) of the minimum M(x,y) of a collection F of n continuous bivariate functions f1(x,y), ... , fn(x,y), such that each triple of function graphs intersect in at most s points, and each pair of functions intersect in a curve having at most t singular points. The following is proved. (1) If the intersection curve of each pair of functions intersects each plane x = const in exactly one point and s = 1 (but not if s = 2) then κ(F) is at most O(n), and can be calculated in time 0(n log n) by a method extending Shamos' algorithm for the calculation of planar Voronoi diagrams, (2) If s = 2 and the intersection of each pair of functions is connected then κ(F)= 0(n2). (3) If the intersection curve of each pair of functions intersects every plane x = const in at most two points, then κ(F) is at most O(nλs+2(n)), where the constant of proportionality depends on s and t, and where λ,(q) is the (almost linear) maximum length of a (q,r) Davenport-Schinzel sequence. We also present an algorithm for calculating M in this case, running in time O(nλs+2(n) log n). (4) Finally, we present some geometric applications of these results.

New techniques are described for model-based recognition of the objects in 3-D space. The recognition is performed from single gray-scale images taken from unknown viewpoints. The objects in the scene may be overlapping and partially occluded. An efficient matching algorithm, which assumes affine approximation to the prospective viewing transformation, is proposed. The algorithm has an offline model preprocessing (shape representation) phase which is independent of the scene information and a recognition phase based on efficient indexing. It has a straightforward parallel implementation. The algorithm was successfully tested in recognition of industrial objects appearing in composite occluded scenes.>

Novel techniques are described for model-based recognition of 3-D objects from unknown viewpoints using single-gray-scale images. The objects in the scene may be overlapping and partially occluded. Efficient matching algorithms, which assume affine approximation to the perspective viewing transformation, are proposed. The study is currently restricted to flat rigid 3-D objects. Point, line and curve matching algorithms are presented. The study especially emphasizes the curve matching problem. Experimental results are included.>

An approach to manipulation tasks involving dextrous hands is presented. This approach treats the gripped object as a virtual finger and hence reduces the description of the task objectives to target forces and torques at reference points on the object. Computations are carried out for the case of three fingers holding a planar object. The authors implemented these ideas on the Four Finger Manipulator at New York University. Experimental results are presented for door opening and wall following with a gripped tool.>

Techniques are described for model-based recognition of 3-D objects from unknown viewpoints using single gray-scale images. The method is especially useful for recognition of scenes with overlapping and partially occluded objects. An efficient matching algorithm, which assumes affine approximation to the perspective viewing transformation, is proposed. The algorithm has an off line model preprocessing phase and a recognition phase to reduce matching complexity. The algorithm was successfully tested in recognition of flat industrial objects appearing in composite occluded scenes.>

We consider the problem of obtaining sharp (nearly quadratic) bounds for the combinatorial complexity of the lower envelope (i.e. pointwise minimum) of a collection of n bivariate (or generally multi-variate) continuous and "simple" functions, and of designing efficient algorithms for the calculation of this envelope. This problem generalizes the well-studied univariate case (whose analysis is based on the theory of Davenport-Schinzel sequences), but appears to be much more difficult and still largely unsolved. It is a central problem that arises in many areas in computational and combinatorial geometry, and has numerous applications including generalized planar Voronoi diagrams, hidden surface elimination for intersecting surfaces, purely translational motion planning, finding common transversals of polyhedra, and more. In this abstract we provide several partial solutions and generalizations of this problem, and apply them to the problems mentioned above. The most significant of our results is that the lower envelope of n triangles in three dimensions has combinatorial complexity at most O(n2α(n)) (where α(n) is the extremely slowly growing inverse of Ackermann's function), that this bound is tight in the worst case, and that this envelope can be calculated in time O(n2α(n)).

Etude des procedures de decision pour differents sous-langages restreints quantifies et non quantifies de la theorie des ensembles

Experimental results for the recognition of general curves in three-space using registered range and intensity images are presented. the matching algorithm uses fast Fourier transforms to determine the least-squares difference between sequences of points sampled at equal intervals along two piecewise linear approximations of curves in three-space and returns the rotation and translation required to bring one of the curves into closest juxtaposition with the other. Performance of the algorithm is demonstrated by matching curves in three-space which are the boundaries of regions of contrasting reflectivity on curved surfaces. the experiments use a recently developed range sensor which is able to generate a 512 × 460 × 12 bit range image (with registered intensity image) in 40 s.

The structure of an existing optimizer for the very high-level, set theoretically oriented programming language SETL is described, and its capabilities are illustrated.The use of novel techniques (supported by state-of-the-art interprocedural program analysis methods) enables the optimizer to accomplish various sophisticated optimizations, the most significant of which are the automatic selection of data representations and the systematic elimination of superfluous copying operations.These techniques allow quite sophisticated data-structure choices to be made automatically.

SETL is a very-high-level programming language supporting set-theoretic syntax and semantics.It allows algorithms to be programmed rapidly and succinctly without requiring data-structure declarations to be supplied.Such declarations can be manually specified later, without recoding the program, to improve the efficiency of program execution.We describe a new technique for automatic selection of appropriate data representations during compile time for programs with omitted declarations and present an efficient data representation selection algorithm, whose complexity is comparable with those of the fastest known general data-flow algorithms of Tarjan and Reif.

The starthng success of the Rabm-Strassen-Solovay pnmahty algorithm, together with the intriguing foundattonal posstbthty that axtoms of randomness may constttute a useful fundamental source of mathemaucal truth independent of the standard axmmaUc structure of mathemaUcs, suggests a wgorous search for probabdisuc algonthms In dlustratmn of this observaUon, vanous fast probabdlsttc algonthms, with probability of correctness guaranteed a prion, are presented for testing polynomial ldentmes and propemes of systems of polynomials.Ancdlary fast algorithms for calculating resultants and Sturm sequences are given.Probabilistlc calculatton in real anthmetlc, prewously considered by Davis, is justified ngorously, but only in a special case.Theorems of elementary geometry can be proved much more efficiently by the techmques presented than by any known arttficml-mtelhgence approach

A class of parallel processors potentially involving thousands of individual processing elements is described. The architecture is based on the perfect shuffle connection and has two favorable characteristics: (1) Each processor communicates with a fixed number of other processors. (2) Important communication functions can be accomplished in time proportional to the logarithm of the number of processors. A number of basic algorithms for these “ultracomputers” are presented, and physical design considerations are discussed in a preliminary fashion.

SETL is a very high level programming language supporting set theoretical syntax and semantics. It allows algorithms to be programmed rapidly and succinctly without requiring data structure declarations to be supplied, though such declarations can be manually specified later, without recoding the program, to improve the efficiency of program execution. We describe a new technique for automatic selection of appropriate data representations during compile-time for undeclared, or partially declared programs,and present an efficient data structure selection algorithm, whose complexity is comparable with those of the fastest known general data-flow algorithms of Tarjan [TA2] and Reif [RE].

“Pure” SETL is a language of very high level allowing algorithms to be programmed rapidly and succintly. SETL's representation sublanguage adds a system of declarations which allow the user of the language to control the data structures that will be used to implement an algorithm which has already been written in pure SETL, so as to improve its efficiency. Ideally no rewriting of the algorithm should be necessary. The facilities provided by the representation sublanguage and the run-time data structures that it can generate are described; based on this a heuristic which uses some of the methods of global program analysis and which should be capable of selecting an acceptably efficient representation automatically is given.

SETL is a set-theoretically oriented language of very high level whose repertoire of semantic objects includes finite sets, ordered n-tuples, and sets of ordered n-tuples useable as mappings. This paper sets forth techniques for the logical analysis and optimization of SETL programs. The techniques described allow relations of inclusion and membership to be established, the domains and ranges of (tabulated) mappings to be estimated from above and below, and the singlevaluedness of (tabulated) mappings to be proved. Once facts of this kind have been established, automatic choice of data structures becomes possible. The methods employed are based upon, and extend, known techniques of data-flow analysis.