S. K. Abdali, G. W. Cherry, Alok Aggarwal, Leonidas J. Guibas, James Saxe, Alfred V. Aho, ...
[2] Habib Abdulrab and Jean-Pierre P'ecuchet. Solving word equations. In Claude Kirchner,
CSI 409 – Automata and Formal Languages – Fall 2007 Course Policies (2008)
John E. Hopcroft, Rajeev Motwani
Textbook:
Computer Algorithms. Addison-Wesley, 1974. (2008)
Milton Abramowitz, Irene A. Stegun, Leonard M. Adleman, Carl Pomerance, ...
numbers from composite numbers. Annals of Mathematics, 117:173–206, 1983. [4] Alok Aggarwal and Jeffrey Scott Vitter. The input/output complexity of sorting and related problems. Communications of...
A Linear List Merging Algorithm (2008)
Hopcroft, John E., Ullman, Jeffrey D.
A linear list merging algorithm and its analysis is presented. Starting with n lists, each containing a single element, the algorithm will execute an arbitrary sequence of requests to merge lists and...
A Linear List Merging Algorithm (2008)
Hopcroft, John E., Ullman, Jeffrey D.
A linear list merging algorithm and its analysis is presented. Starting with n lists, each containing a single element, the algorithm will execute an arbitrary sequence of requests to merge lists and...
Jean-raymond Abrial, Stephen A. Schuman, In On The, Alfred V. Aho, John E. Hopcroft
This bibliography has two parts: works by other authors; works by the author of the present book. See also, in the chapter on inheritance methodology (page 868), a list of references on...
Adobe Systems Incorporated. TIFF (Tagged Image File Format) 6.0 Specification. Adobe (2008)
Alfred V. Aho, John E. Hopcroft, Jeffrey Ullman, Data Structures, Christopher Alex, Sara Ishikawa, ...
Robust Iterators in ET++ 35 References (2007)
Liskov Barbara Liskov, John Guttag Abstraction, Specification In Program, Jeffrey Scott, Vitter Maximum, ...
View (California), 1990.
Alfred V. Aho, John E. Hopcroft
This paper has described algorithms for putting data into heap order in the (randomized) parallel comparison tree model. The deterministic algorithm is optimal in time and work, achieving 0(log log...
SYNTHESIS OF THRESHOLD LOGIC NETWORKS, (2005)
The purpose of the research described in this report is to develop an algorithm for synthesizing Boolean switching functions with a minimum number of threshold logic units, and to apply the algorithm...
A Linear Algorithm for Testing Equivalence of Finite Automata. (2005)
Hopcroft,John E., Karp,Richard M.
An algorithm is given for determining if two finite automata with start states are equivalent. The asymptotic running time of the algorithm is bounded by a constant times the product of the number of...
Spectral analysis of random Graphs with skewed degree distributions (2004)
Anirban Dasgupta, John E. Hopcroft, Frank Mcsherry
We extend spectral methods to random graphs with skewed degree distributions through a degree based normalization closely connected to the normalized Laplacian. The normalization is based on...
Merging on Parallel Models of Computation. (2002)
Hopcroft,John E., Borodin,Allan
A variety of models have been proposed for the study of synchronous parallel computation. We review these models and study further some prototype problems. Within a spectrum of shared memory models,...
Hopcroft,John E., Borodin,Allan
This report is concerned with routing protocols in networks. The major result is a low bound for any oblivious routing strategy where the route of a packet depends only on the source and destination...
Movement Problems for 2-Dimensional Linkages. (2002)
Hopcroft,John E., Joseph,Deborah A., Whitesides,Sue H.
This paper is motivated by questions concerning the planning of motion in robotics. In particulra, it is concerned with the motion of planar linkages from the complexity point of view. There are two...
Are randomly grown graphs really random? (2001)
Callaway, Duncan S., Hopcroft, John E., Kleinberg, Jon M., Newman, M. E. J., Strogatz, Steven H.
We analyze a minimal model of a growing network. At each time step, a new vertex is added; then, with probability delta, two vertices are chosen uniformly at random and joined by an undirected edge....
Textbooks: 1. Introduction to Automata Theory, Languages, and Computation (2000)
Prepared Lesson Plans, John E. Hopcroft, H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Topics: Selected Reference References The following books are useful references. (2000)
Alfred V. Aho, John E. Hopcroft
but it lacks topics in network flows and linear programming, as well as more recent algorithms. It is amazing that after more than twenty years it remains an extremely valuable book. 2. Alfred V....
Finding the Triconnected Components of a Graph, (1998)
Hopcroft,John E., Tarjan,Robert E.
An algorithm for decomposing a graph into triconnected components is presented. The algorithm requires 0(V + E) time and space when implemented on a random access computer, where V is the number of...
Triangular Factorization and Inversion by Fast Matrix Multiplication. (1998)
Bunch,James R., Hopcroft,John E.
The fast matrix multiplication algorithm by Strassen is used to obtain the triangular factorization of a permutation of any non-singular matrix of order n in (C sub 1)(n sup(log of 7 to the base 2))...
Fast Parallel Matrix and GCD Computations. (1998)
Borodin,Allan, Von Zur Gathen,Joachim, Hopcroft,John E.
We present parallel algorithms to compute the determinant and characteristics polynomial of nxn-matrices and the gcd of polynomials of degree less than or equal n. The algorithms use parallel time...
On the Movement of Robot Arms in 2-Dimensional Bounded Regions. (1998)
Hopcroft,John E., Joseph,Deborah A., Whitesides,Sue H.
The classical mover's problem is the following: can a rigid object in 3-dimensional space be moved from one given position to another while avoiding obstacles? It is known that a more general version...
On Planar Point Matching under Affine Transformation. (1998)
Hopcroft, John E., Huttenlocher, Daniel P.
An important geometric matching problem in machine vision and robotics is to determine whether there exists an affine transformation (a general linear transformation and a translation) that maps each...
Contents: Improving the Simulation Simulation; Anthropoid Walking; Parallel, Distributed Control of Complex Systems; Solid Modeler Robustness; Finite Element Method; Swept Volumes. (KR)
The most significant development in the past three months has been our group's commitment to develop a uniform platform for specifying geometric objects and operations. The necessity for such a...
A Paradigm for Robust Geometric Algorithms, (1998)
Hopcroft, John E., Kahn, Peter J.
Geometrical algorithms in use in computer aided design systems today often fail for numerical reasons. The cause of these failures usually can be traced to logical decisions such as branch on zero...
A Case Study of Flexible Object Manipulation, (1998)
Hopcroft, John E., Kearney, Joseph K., Krafft, Dean B.
This paper describes a project undertaken to explore programming physical operations on complex flexible objects. Uncertainty about the exact state of the object makes it impossible to precisely...
Using Computer Design and Simulation to Improve Manufacturing Productivity. (1998)
Our work on Simulaid, our simulator generation environment, is continuing. During the past quarter, we have implemented a prototype simulation environment and used it to construct a simple...
Quarterly R and D Status Report, April 1991 (Cornell University), (1998)
Contents: Robust Solid Modeling; Shape Control in Implicit Modeling; Control of complex Objects.
One of the great deficiencies of today's robots is their lack of flexibility. Most industrial robots are capable only of simple and repetitive tasks, such as spot welding or spray painting. There are...
The Cornell Computer Science Modeling and Simulation Project was founded on the belief that electronic prototypes would have a significant impact on our nation's technological growth. From the...
The Cornell Computer Science Modeling and Simulation Project was founded on the belief that electronic prototypes would have a significant impact on our nation's technological growth. From the...
Using Computer Design and Simulation to Improve Manufacturing Productivity. (1998)
The members of the Modeling and Simulation Group at Cornell believe that improvements in computer capabilities and in software design tools have the potential to radically alter the manufacturing...
Estructuras de datos y algoritmos (1998)
Aho, Alfred V., Hopcroft, John E., Ullman, Jeffrey D.
Contenido: Diseño y análisis de algoritmos; Tipos de datos abstractos fundamentales; Arboles; Operaciones básicas con conjuntos; Métodos avanzados de representación de conjuntos; Grafos...
Estructuras de datos y algoritmos (1998)
Aho, Alfred V., Hopcroft, John E., Ullman, Jeffrey D.
968-444-345-5
A Paradigm for Robust Geometric Algorithms (1989)
Hopcroft, John E., Kahn, Peter J.
No abstract is available.
A Paradigm for Robust Geometric Algorithms (1989)
Hopcroft, John E., Kahn, Peter J.
No abstract is available.
Logic Programming over Polymorphically Order-Sorted Types (1989)
This thesis presents the foundations for relational logic programming over polymorphically order-sorted data types. This type discipline combines the notion of parametric polymorphism, which has been...
Aho, Alfred V, Hopcroft, John E, Ullman, Jeffrey D
Traducción de: "Data structures and algoritms"
Robust Set Operations on Polyhedral Solids (1987)
Hoffmann, Christoph M., Hopcroft, John E., Karasick, Michael S.
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...
Robust Set Operations on Polyhedral Solids (1987)
Hoffmann, Christoph M., Hopcroft, John E., Karasick, Michael S.
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...
The Geometry of Projective Blending Surfaces (1986)
Hoffmann, Christoph M., Hopcroft, John E.
Blending surfaces smoothly join two or more primary surfaces that otherwise would intersect in edges. We outline the potential method for deriving blending surfaces, and explain why the method needs...
The Geometry of Projective Blending Surfaces (1986)
Hoffmann, Christoph M., Hopcroft, John E.
Blending surfaces smoothly join two or more primary surfaces that otherwise would intersect in edges. We outline the potential method for deriving blending surfaces, and explain why the method needs...
Geometric Ambiguities in Boundary Representations (1986)
Hoffmann, Christoph M., Hopcroft, John E.
Boundary representations are usually separated into two components, a topological component and a geometric component. The conditions necessary to insure that the topological component is unambiguous...
Geometric Ambiguities in Boundary Representations (1986)
Hoffmann, Christoph M., Hopcroft, John E.
Boundary representations are usually separated into two components, a topological component and a geometric component. The conditions necessary to insure that the topological component is unambiguous...
The Potential Method for Blending Surfaces and Corners (1985)
Hoffmann, Christoph M., Hopcroft, John E.
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,...
The Potential Method for Blending Surfaces and Corners (1985)
Hoffmann, Christoph M., Hopcroft, John E.
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,...
Automatic Surface Generation in Computer Aided Design (1985)
Hoffmann, Christoph M., Hopcroft, John E.
No abstract available
Automatic Surface Generation in Computer Aided Design (1985)
Hoffmann, Christoph M., Hopcroft, John E.
No abstract available
Reducing Multiple Object Motion Planning To Graph Searching (1984)
Hopcroft, John E., Wilfong, Gordon
In this paper we study the motion planning problem for multiple objects where an object is a 2-dimensional body whose faces are line segments parallel to the axes of $R^{2}$ and translations are the...
Reducing Multiple Object Motion Planning To Graph Searching (1984)
Hopcroft, John E., Wilfong, Gordon
In this paper we study the motion planning problem for multiple objects where an object is a 2-dimensional body whose faces are line segments parallel to the axes of $R^{2}$ and translations are the...
On the Motion of Objects in Contact (1984)
Hopcroft, John E., Wilfong, Gordon
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....
On the Motion of Objects in Contact (1984)
Hopcroft, John E., Wilfong, Gordon
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....
Data Structures and Algorithms (1983)
Aho, Alfred V., Hopcroft, John E., Ullman, Jeffrey D.
Este libro presenta la estructura de datos y algoritmos que apoyan a muchos de los programas de computación.
Data Structures and Algorithms / A.V. Aho, J.E. Hopcroft, J.D. Ullman. (1983)
Aho, Alfred V., Hopcroft, John E., Ullman, Jeffrey D.
Este libro presenta la estructura de datos y algoritmos que apoyan a muchos de los programas de computación.
Projektowanie i analiza algorytmów komputerowych (1983)
Aho, Alfred V. (1941- ), Hopcroft, John E. (1939- ), Ullman, Jeffrey D. (1942- )
Movement Problems for 2-Dimensional Linkages (1982)
Hopcroft, John E., Joseph, Deborah A., Whitesides, Sue H.
NO ABSTRACT SUPPLIED
Determining Points of a Circular Region Reachable by Joints of a Robot Arm (1982)
Hopcroft, John E., Joseph, Deborah A., Whitesides, Sue H.
An "arm" is a sequence of links whose endpoints are connected consecutively by movable joints. The location of the first endpoint is fixed. This report gives a polynomial time algorithm for...
Movement Problems for 2-Dimensional Linkages (1982)
Hopcroft, John E., Joseph, Deborah A., Whitesides, Sue H.
NO ABSTRACT SUPPLIED
Determining Points of a Circular Region Reachable by Joints of a Robot Arm (1982)
Hopcroft, John E., Joseph, Deborah A., Whitesides, Sue H.
An "arm" is a sequence of links whose endpoints are connected consecutively by movable joints. The location of the first endpoint is fixed. This report gives a polynomial time algorithm for...
On the Movement of Robot Arms in Two Dimensional Bounded Regions (1982)
Hopcroft, John E., Joseph, Deborah A., Whitesides, Sue H.
The classical mover's problem is the following: can a rigid object in 3-dimensional space be moved from one given position to another while avoiding obstacles? It is known that a more general version...
Fast Parallel Matrix and GCD Computations (1982)
Borodin, Allan B., Von Zur Gathen, Joachim, Hopcroft, John E.
We present parallel algorithms to compute the determinant and characteristic polynomial of n x n-matrices and the gcd of polynomials of degree $\leq$n. The algorithms use parallel time $O(\log^{2}n)$...
On the Movement of Robot Arms in Two Dimensional Bounded Regions (1982)
Hopcroft, John E., Joseph, Deborah A., Whitesides, Sue H.
The classical mover's problem is the following: can a rigid object in 3-dimensional space be moved from one given position to another while avoiding obstacles? It is known that a more general version...
Fast Parallel Matrix and GCD Computations (1982)
Borodin, Allan B., Von Zur Gathen, Joachim, Hopcroft, John E.
We present parallel algorithms to compute the determinant and characteristic polynomial of n x n-matrices and the gcd of polynomials of degree $\leq$n. The algorithms use parallel time $O(\log^{2}n)$...
Merging on Parallel Models of Computation (1981)
Borodin, Allan B., Hopcroft, John E.
A variety of models have been proposed for the study of synchronous parallel computation. We review these models and study further some prototype problems. Within a spectrum of shared memory models,...
Merging on Parallel Models of Computation (1981)
Borodin, Allan B., Hopcroft, John E.
A variety of models have been proposed for the study of synchronous parallel computation. We review these models and study further some prototype problems. Within a spectrum of shared memory models,...
Polynomial-Time Algorithms for Permutation Groups (1980)
Furst, Merrick, Hopcroft, John E., Luks, Eugene
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...
Polynomial-Time Algorithms for Permutation Groups (1980)
Furst, Merrick, Hopcroft, John E., Luks, Eugene
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...
A Subexponential Algorithm for Trivalent Graph Isomorphism (1980)
Furst, Merrick, Hopcroft, John E., Luks, Eugene
NO ABSTRACT SUPPLIED
A Subexponential Algorithm for Trivalent Graph Isomorphism (1980)
Furst, Merrick, Hopcroft, John E., Luks, Eugene
NO ABSTRACT SUPPLIED
A Linear Time Algorithm for the Generalized Consecutive Retrieval Problem (1979)
Dietz, Paul F., Furst, Merrick, Hopcroft, John E.
THe Generalized Consecutive Retrieval Problem (GCRP) is to find a directed tree on $n$ records in which each of $k$ subsets forms a directed path. The problem arises in organizing information for...
A Linear Time Algorithm for the Generalized Consecutive Retrieval Problem (1979)
Dietz, Paul F., Furst, Merrick, Hopcroft, John E.
THe Generalized Consecutive Retrieval Problem (GCRP) is to find a directed tree on $n$ records in which each of $k$ subsets forms a directed path. The problem arises in organizing information for...
Hopcroft, John E, Ullman, Jeffrey D
Incluye bibliografía e índice
A Note on Cryptography and NP$\cap$ CoNP-P (1978)
Brassard, Giles, Fortune, Steven, Hopcroft, John E.
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...
A Note on Rabin's Nearest-Neighbor Algorithm (1978)
Fortune, Steven, Hopcroft, John E.
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...
A Note on Cryptography and NP$\cap$ CoNP-P (1978)
Brassard, Giles, Fortune, Steven, Hopcroft, John E.
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...
A Note on Rabin's Nearest-Neighbor Algorithm (1978)
Fortune, Steven, Hopcroft, John E.
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...
The Complexity of Equivalence and Containment for Free Single Variable Program Schemes (1977)
Fortune, Steven, Hopcroft, John E., Schmidt, Erik Meineche
Non-containment for free single variable program schemes is shown to be NP-complete. A polynomial time algorithm for deciding equivalence of two free schemes, provided one of them has the predicates...
The Complexity of Equivalence and Containment for Free Single Variable Program Schemes (1977)
Fortune, Steven, Hopcroft, John E., Schmidt, Erik Meineche
Non-containment for free single variable program schemes is shown to be NP-complete. A polynomial time algorithm for deciding equivalence of two free schemes, provided one of them has the predicates...
Independence Results in Computer Science (1976)
Hartmanis, Juris, Hopcroft, John E.
In this note we show that instances of problems which appear naturally in computer science cannot be answered in formalized set theory. We show, for example, that some relativized versions of the...
Independence Results in Computer Science (1976)
Hartmanis, Juris, Hopcroft, John E.
In this note we show that instances of problems which appear naturally in computer science cannot be answered in formalized set theory. We show, for example, that some relativized versions of the...
On the Reachability Problem for 5-Dimensional Vector Addition Systems (1976)
Hopcroft, John E., Pansiot, J.
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...
On the Reachability Problem for 5-Dimensional Vector Addition Systems (1976)
Hopcroft, John E., Pansiot, J.
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...
Hopcroft, John E., Paul, Wolfgang J., Valiant, Leslie
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...
Hopcroft, John E., Paul, Wolfgang J., Valiant, Leslie
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...
Dividing a Graph into Triconnected Components (1974)
Hopcroft, John E., Tarjan, Robert Endre
An algorithm for dividing a graph into triconnected components is presented. When implemented on a random access computer, the algorithm requires $O(V+E)$ time and space to analyze a graph with $V$...
Dividing a Graph into Triconnected Components (1974)
Hopcroft, John E., Tarjan, Robert Endre
An algorithm for dividing a graph into triconnected components is presented. When implemented on a random access computer, the algorithm requires $O(V+E)$ time and space to analyze a graph with $V$...
The design and analysis of computer algorithms (1974)
Aho, Alfred V., Hopcroft, John E., Vilman, Jeffrey D.
La intención de este libro es unir los resultados fundamentales en el área de algoritmos, para unificar principios y resaltar conceptos de diseño de algoritmos y así se haga más fácil la...
The design and analysis of computer algorithms / A.V. Aho, J.E. Hopcroft, J.D. Ullman. (1974)
Aho, Alfred V., Hopcroft, John E., Ullman, Jeffrey D.
La intención de este libro es unir los resultados fundamentales en el área de algoritmos, para unificar principios y resaltar conceptos de diseño de algoritmos y así se haga más fácil la...
Efficient Planarity Testing (1973)
Hopcroft, John E., Tarjan, Robert Endre
This paper describes an efficient algorithm to determine whether an arbitrary graph G can be embedded in the plane. The algorithm may be viewed as an iterative version of a method originally proposed...
Efficient Planarity Testing (1973)
Hopcroft, John E., Tarjan, Robert Endre
This paper describes an efficient algorithm to determine whether an arbitrary graph G can be embedded in the plane. The algorithm may be viewed as an iterative version of a method originally proposed...
Triangular Factorization and Inversion by Fast Matrix Multiplication (1972)
Bunch, James R., Hopcroft, John E.
The fast matrix multiplication algorithm by Strassen is used to obtain the triangular factorization of a permutation of any non-singular matrix of order n in "greater than" C sub{1}n sup{log sub{2}7}...
Triangular Factorization and Inversion by Fast Matrix Multiplication (1972)
Bunch, James R., Hopcroft, John E.
The fast matrix multiplication algorithm by Strassen is used to obtain the triangular factorization of a permutation of any non-singular matrix of order n in "greater than" C sub{1}n sup{log sub{2}7}...
Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms (1972)
Hopcroft, John E., Musinski, J.
The paper considers the complexity of bilinear forms in a noncommutative ring. The dual of a computation is defined and applied to matrix multiplication and other bilinear forms. It is shown that the...
Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms (1972)
Hopcroft, John E., Musinski, J.
The paper considers the complexity of bilinear forms in a noncommutative ring. The dual of a computation is defined and applied to matrix multiplication and other bilinear forms. It is shown that the...
A Linear Algorithm for Testing Equivalence of Finite Automata (1971)
Hopcroft, John E., Karp, R. M.
An algorithm is given for determining if two finite automata with start states are equivalent. The asymptotic running time of the algorithm is bounded by a constant times the product of the number of...
A Linear Algorithm for Testing Equivalence of Finite Automata (1971)
Hopcroft, John E., Karp, R. M.
An algorithm is given for determining if two finite automata with start states are equivalent. The asymptotic running time of the algorithm is bounded by a constant times the product of the number of...
An Overview of the Theory of Computational Complexity (1970)
Hartmanis, Juris, Hopcroft, John E.
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...
An Overview of the Theory of Computational Complexity (1970)
Hartmanis, Juris, Hopcroft, John E.
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...
On Minimizing the Number of Multiplications Necessary for Matrix Multiplication (1969)
Hopcroft, John E., Kerr, Leslie Robert
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...
On Minimizing the Number of Multiplications Necessary for Matrix Multiplication (1969)
Hopcroft, John E., Kerr, Leslie Robert
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...
Formal languages and their relation to automata / John E. Hopcroft, Jeffre D. Ullman (1969)
Hopcroft, John E, Ullman, Jaffrey D
Incluye bibliografía e índice
On the Equivalence and Containment Problems for Context-Free Languages (1968)
Let $G$ and $G_{0}$ be context-free 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...
Refinement of Hierarchies of Time Bounded Computations (1968)
Hartmanis, Juris, Hopcroft, John E.
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)$...
On the Equivalence and Containment Problems for Context-Free Languages (1968)
Let $G$ and $G_{0}$ be context-free 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...
Refinement of Hierarchies of Time Bounded Computations (1968)
Hartmanis, Juris, Hopcroft, John E.
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)$...
Introducción a la Teoría de Autómatas, Lenguajes y Computación (0000)
TABLA DE CONTENIDO TABLA DE CONTENIDO PARA QUE SIRVEN LOS AUTÓMATAS? AUTÓMATAS FIFNITOS EXPRESIONES Y LENGUAJES REGULARES PROPIEDADES DE LOS LENGUAJES REGULARES GRAMÁTICAS...
Introducción a la Teoría de Autómatas, Lenguajes y Computación
TABLA DE CONTENIDO TABLA DE CONTENIDO PARA QUE SIRVEN LOS AUTÓMATAS? AUTÓMATAS FIFNITOS EXPRESIONES Y LENGUAJES REGULARES PROPIEDADES DE LOS LENGUAJES REGULARES...