JavaScript is disabled for your browser. Some features of this site may not work without it.
Browsing by Author "Hopcroft, John E."
Now showing items 1736 of 37

A Note on Cryptography and NP$\cap$ CoNPP
Brassard, Giles; Fortune, Steven; Hopcroft, John E. (Cornell University, 197804)Diffie and Hellman [2] propose the use of the exponential function in a finite field for cryptographic purposes. The proposal is based on the conjecture that the inverse function, the logarithm, is not feasibly computable. ... 
A Note on Rabin's NearestNeighbor Algorithm
Fortune, Steven; Hopcroft, John E. (Cornell University, 197804)Rabin has proposed a probabilistic algorithm for finding the closest pair of a set of points in Euclidean space. His algorithm is asymtomatically linear whereas the best of the known deterministic algorithms take order ... 
On Edge Coloring Bipartite Graphs
Cole, Richard; Hopcroft, John E. (Cornell University, 198011)NO ABSTRACT SUPPLIED 
On Minimizing the Number of Multiplications Necessary for Matrix Multiplication
Hopcroft, John E.; Kerr, Leslie Robert (Cornell University, 196909)This paper develops an algorithm to multiply a px2 matrix by a 2xn matrix in $\lceil (3pn+max(n,p))/2 \rceil$ multiplications for matrix multiplication without commutativity. The algorithm minimizes the number of multiplications ... 
On Planar Point Matching Under Affine Transformation
Hopcroft, John E.; Huttenlocher, Daniel P. (Cornell University, 198904) 
On the Equivalence and Containment Problems for ContextFree Languages
Hopcroft, John E. (Cornell University, 196806)Let $G$ and $G_{0}$ be contextfree grammars. Necessary and sufficient conditions on $G_{0}$ are obtained for the decidability of $L(G_{0}) \subseteq L(G)$. It is also shown that it is undecidable for which $G_{0},L(G) ... 
On the Motion of Objects in Contact
Hopcroft, John E.; Wilfong, Gordon (Cornell University, 198405)There is an increasing use of computers in the design, manufacture and manipulation of physical objects. An important aspect of reasoning about such actions concerns the motion of objects in contact. The study of problems ... 
On the Movement of Robot Arms in Two Dimensional Bounded Regions
Hopcroft, John E.; Joseph, Deborah A.; Whitesides, Sue H. (Cornell University, 198204)The classical mover's problem is the following: can a rigid object in 3dimensional space be moved from one given position to another while avoiding obstacles? It is known that a more general version of this problem ... 
On the Reachability Problem for 5Dimensional Vector Addition Systems
Hopcroft, John E.; Pansiot, J. (Cornell University, 197606)The reachability set for vector addition systems of dimension less than or equal to five are shown to be effectively computable semilinear sets. Thus reachability, equvalence and containment are decidable up to dimension ... 
On Time Versus Space
Hopcroft, John E.; Paul, Wolfgang J.; Valiant, Leslie (Cornell University, 197512)It is shown that every deterministic multitape Turing machine of time complexity t(n)/log t(n). Consequently, for tape constructable t(n), the class of languages recognizable by multitape Turing machines of time complexity ... 
An Overview of the Theory of Computational Complexity
Hartmanis, Juris; Hopcroft, John E. (Cornell University, 197004)The purpose of this paper is to outline the theory of computational complexity which has emerged as a comprehensive theory during the last decade. This theory is concerned with the quantitative aspects of computations and ... 
A Paradigm for Robust Geometric Algorithms
Hopcroft, John E.; Kahn, Peter J. (Cornell University, 198910)No abstract is available. 
PolynomialTime Algorithms for Permutation Groups
Furst, Merrick; Hopcroft, John E.; Luks, Eugene (Cornell University, 198010)A permutation group on n letters may always be represented by a small set of generators, even though its size may be exponential in n. We show that it is practical to use such a representation since many problems such ... 
The Potential Method for Blending Surfaces and Corners
Hoffmann, Christoph M.; Hopcroft, John E. (Cornell University, 198509)We survey the potential method for blending implicit algebraic surfaces, summarizing and extending work previously reported. The method is capable of deriving blends for pairs of algebraic surfaces, and is guaranteed to ... 
Quadratic Blending Surfaces
Hoffmann, Christoph M.; Hopcroft, John E. (Cornell University, 198504)ABSTRACT NOT SUPPLIED 
Reducing Multiple Object Motion Planning To Graph Searching
Hopcroft, John E.; Wilfong, Gordon (Cornell University, 198406)In this paper we study the motion planning problem for multiple objects where an object is a 2dimensional body whose faces are line segments parallel to the axes of $R^{2}$ and translations are the only motions allowed. ... 
Refinement of Hierarchies of Time Bounded Computations
Hartmanis, Juris; Hopcroft, John E. (Cornell University, 196806)It is shown that for any "slowly growing" time function $T(n)$ and any $\epsilon > 0$ there exists a computation which can be performed by a multitape Turing machine in time $T(n)\log^{\epsilon}T(n)$ and cannot be performed ... 
Robust Set Operations on Polyhedral Solids
Hoffmann, Christoph M.; Hopcroft, John E.; Karasick, Michael S. (Cornell University, 198710)We describe an algorithm for performing regularized set operations on polyhedral solids. Robustness of this algorithm is achieved by adding symbolic reasoning as a supplemental step that compensates for possible numerical ... 
Routing in Networks
Borodin, Allan B.; Hopcroft, John E. (Cornell University, 198111)NO ABSTRACT SUPPLIED 
A Subexponential Algorithm for Trivalent Graph Isomorphism
Furst, Merrick; Hopcroft, John E.; Luks, Eugene (Cornell University, 198006)NO ABSTRACT SUPPLIED