scientific article; zbMATH DE number 3449757

Jeffrey D. Ullman, John E. Hopcrofts, A. V. Aho

Publication date: 1969

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10)

Related Items

Length-bounded disjoint paths in planar graphs ⋮ More efficient PAC-learning of DNF with membership queries under the uniform distribution ⋮ An inversion formula and fast algorithms for Cauchy-Vandermonde matrices ⋮ An efficient basis update for asymptotic linear programming ⋮ The recognition of union trees ⋮ Resource allocation via dynamic programming in activity networks ⋮ The complexity of assigning genotypes to people in a pedigree consistently ⋮ Algorithms for weakly triangulated graphs ⋮ Efficient computation of an isotonic median regression ⋮ Single step searching in weighted block graphs ⋮ Cost-optimal parallel algorithms for constructing B-trees ⋮ A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths ⋮ On the range maximum-sum segment query problem ⋮ Deadlocks and traps in Petri nets as Horn-satisfiability solutions and some related polynomially solvable problems ⋮ Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant ⋮ Computing half-plane and strip discrepancy of planar point sets ⋮ The weighted perfect domination problem and its variants ⋮ Optimal and nearly optimal algorithms for approximating polynomial zeros ⋮ Decomposition of a bidirected graph into strongly connected components and its signed poset structure ⋮ Solving a vehicle routing problem by balancing the vehicles time utilization. ⋮ Algorithmic approach to counting of certain types \(m\)-ary partitions. ⋮ A modular reduction for GCD computation. ⋮ Computing the sign or the value of the determinant of an integer matrix, a complexity survey. ⋮ A note on computing graph closures ⋮ Dynamic programming on a functional memory computer ⋮ The obnoxious center problem on weighted cactus graphs. ⋮ Skolem functions of arithmetical sentences. ⋮ Graph isomorphism and identification matrices: Sequential algorithms ⋮ A survey on the continuous nonlinear resource allocation problem ⋮ Solving hyperbolic PDE's on hypercubes ⋮ Counting truth assignments of formulas of bounded tree-width or clique-width ⋮ A survey of computational complexity results in systems and control ⋮ AVL trees with relaxed balance ⋮ Reoptimization in Lagrangian methods for the \(0\)-\(1\) quadratic knapsack problem ⋮ An efficient algorithm for minimizing earliness, tardiness, and due-date costs for equal-sized jobs ⋮ Efficient parallel factorization and solution of structured and unstructured linear systems ⋮ The determinant of a unicyclic graph's neighborhood matrix ⋮ Structuring product development processes ⋮ Fast connected-component labeling ⋮ Fully dynamic all pairs shortest paths with real edge weights ⋮ On the severity of Braess's paradox: designing networks for selfish users is hard ⋮ An efficient representation for implementing finite state machines based on the double-array ⋮ The computational complexity of the criticality problems in a network with interval activity times ⋮ Boolean expression diagrams ⋮ World-championship-caliber Scrabble* ⋮ On the relationship between model-based debugging and program slicing ⋮ Group centre and group median of a tree ⋮ Generating hard and diverse test sets for NP-hard graph problems ⋮ A self-stabilizing algorithm for detecting fundamental cycles in a graph ⋮ A characterization of Markov equivalence for directed cyclic graphs ⋮ Matrix multiplication for finite algebraic systems ⋮ Resolution deduction to detect satisfiability for another class including non-Horn sentences in propositional logic ⋮ Fast and efficient parallel evaluation of the zeros of a polynomial having only real zeros ⋮ On efficient parallel computations of costs of paths on a grid graph ⋮ On the orderability problem for PLA folding ⋮ Data structures in real-time environment ⋮ The heap-mergesort ⋮ Fuzzy linear systems ⋮ On the transformation semigroups of finite automata ⋮ A linear algorithm for the domination number of a series-parallel graph ⋮ Scheduling unit-time tasks with integer release times and deadlines ⋮ Polynomial complete problems in automata theory ⋮ Insertion-safeness in balanced trees ⋮ Solving covering problems and the uncapacitated plant location problem on trees ⋮ On the NP-hardness of edge-deletion and -contraction problems ⋮ Time complexity of loop-free two-way pushdown automata ⋮ A simulation result for two-way pushdown automata ⋮ A data structure for dynamic range queries ⋮ An approximation algorithm for the Hamiltonian walk problem on maximal planar graphs ⋮ Union and split operations on dynamic trapezoidal maps ⋮ Incremental convex planarity testing ⋮ A new variant of a vehicle routing problem: Lower and upper bounds ⋮ Theory of 2-3 heaps ⋮ The shortest-path problem for graphs with random arc-lengths ⋮ On some complexity properties of N-free posets and posets with bounded decomposition diameter ⋮ Reduction in problem size for ranking alternatives in group decision- making ⋮ The generalized Sprague-Grundy function and its invariance under certain mappings ⋮ A very personal reminiscence on the problem of computational complexity ⋮ On two-dimensional pattern-matching languages and their decision problems ⋮ Graph embedding in SYNCHEM2, an expert system for organic synthesis discovery ⋮ Sequential and parallel complexity of approximate evaluation of polynomial zeros ⋮ Partitioning and separating sets of orthogonal polygons ⋮ An O(n) algorithm for least squares quasi-convex approximation ⋮ Homotopy base of acyclic graphs - a combinatorial analysis of commutative diagrams by means of preordered matroid ⋮ A practical divide-and-conquer algorithm for the rectangle intersection problem ⋮ A fast feasibility test for relocation problems ⋮ Menger-decomposition of a graph and its application to the structural analysis of a large-scale system of equations ⋮ Succinct representation of regular sets using gotos and Boolean variables ⋮ River routing in VLSI ⋮ Scheduling two irregular polygons ⋮ The complexity of computing best-response automata in repeated games ⋮ Lower bound arguments with ``inaccessible numbers ⋮ On induced subgraphs of the cube ⋮ An off-line storage allocation algorithm ⋮ A note on the transaction backout problem ⋮ A new O(n\(\cdot \log \,n)\) algorithm for computing the intersection of convex polygons ⋮ An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits ⋮ A topological approach to dynamic graph connectivity ⋮ Computing dominators in parallel ⋮ A parallel bucket sort ⋮ On generating all maximal independent sets ⋮ Fast string matching with k differences ⋮ On the detection of a common intersection of k convex subjects in the plane ⋮ A practical algorithm for Boolean matrix multiplication ⋮ An improved parallel algorithm that computes the BFS numbering of a directed graph ⋮ The generation of random permutations on the fly ⋮ LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation ⋮ A new application of the extended Euclidean algorithm for matrix Padé approximants ⋮ A note on random sampling ⋮ Shortest path under rational constraint ⋮ Computing the determinant and the characteristic polynomial of a matrix via solving linear systems of equations ⋮ On saving space in parallel computation ⋮ Finding paths and deleting edges in directed acyclic graphs ⋮ Subtree isomorphism is NC reducible to bipartite perfect matching ⋮ An efficient parallel algorithm for random sampling ⋮ Finding a minimum independent dominating set in a permutation graph ⋮ Space measures for storage modification machines ⋮ An \(O(n \log^ 2\,n)\) algorithm for the maximum weighted tardiness problem ⋮ On renaming a set of clauses as a Horn set ⋮ The bit complexity of matrix multiplication and of related computations in linear algebra. The segmented \(\lambda\) algorithms ⋮ Topologically sweeping an arrangement ⋮ Relational decomposition and structural analysis of systems ⋮ Automatic computation of partial derivatives and rounding error estimates with applications to large-scale systems of nonlinear equations ⋮ A maximin procedure for the optimal insertion timing of ad executions ⋮ An optimal design of piping route in a CAD system for power plant ⋮ Lexicographic permutations with restrictions ⋮ Easy and hard bottleneck location problems ⋮ Complexity of problems in games, graphs and algebraic equations ⋮ Characterizations of adjacency on the branching polyhedron ⋮ An algorithm for imbedding cubic graphs in the torus ⋮ Indirect addressing and the time relationships of some models of sequential computation ⋮ A faster algorithm computing string edit distances ⋮ Fast probabilistic algorithms for Hamiltonian circuits and matchings ⋮ An efficient PQ-graph algorithm for solving the graph-realization problem ⋮ Relational consistency algorithms and their application in finding subgraph and graph isomorphisms ⋮ On a cycle finding algorithm ⋮ Lexicographically least circular substrings ⋮ Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete ⋮ On the complexity of testing a graph for n-cube ⋮ Solving the resource constrained deadline scheduling problem via reduction to the network flow problem ⋮ An \(O(EV\log^2V)\) algorithm for the maximal flow problem ⋮ Cellular d-graph automata with augmented memory ⋮ A fast algorithm for solving systems of linear equations with two variables per equation ⋮ Observations on the complexity of regular expression problems ⋮ A complement to Tarjan's result about the lower bound on the complexity of the set union problem ⋮ Finding patterns common to a set of strings ⋮ Asymptotically fast solution of Toeplitz and related systems of linear equations ⋮ On uniform circuit complexity ⋮ On efficient computation of the coefficients of some polynomials with applications to some enumeration problems ⋮ On time versus space. II ⋮ An adversary-based lower bound for sorting ⋮ On minimal augmentation of a graph to obtain an interval graph ⋮ New combinations of methods for the acceleration of matrix multiplication ⋮ A branch and bound algorithm for the acyclic subgraph problem ⋮ Linear decision trees are too weak for convex hull problem ⋮ On the maximum matchings of regular multigraphs ⋮ Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication ⋮ Optimal packing and covering in the plane are NP-complete ⋮ On the time and tape complexity of weak unification ⋮ A fast algorithm for finding all shortest paths ⋮ Complexity of algebraic implementations for abstract data types ⋮ On relaxation methods for systems of linear inequalities ⋮ Some results on relativized deterministic and nondeterministic time hierarchies ⋮ Permutations are not context-free: An application of the interchange lemma ⋮ Explicit constructions of linear-sized superconcentrators ⋮ Space complexity in on-line computation ⋮ Fast matrix multiplication without APA-algorithms ⋮ Finding connected components of an intersection graph of squares in the Euclidean plane ⋮ An algorithm for a merge recognition problem ⋮ Steady-paced-output and fractional-on-line algorithms on a RAM ⋮ Parallel computation and conflicts in memory access ⋮ Discrete ordering relations ⋮ Enumerating the cycles of a digraph: a new preprocessing strategy ⋮ An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function ⋮ An optimal algorithm to compute all the covers of a string ⋮ Complexity of multiplication with vectors for structured matrices ⋮ A clustering heuristic to detect staircase structures in large scale linear programming models ⋮ Linear recognition of pseudo-split graphs ⋮ Bounds on certain multiplications of affine combinations ⋮ An algebraic approach for morphological operations on 2D and 3D images ⋮ On the complexity of computing Gröbner bases in characteristic 2 ⋮ On the equivalence of constrained and unconstrained flows ⋮ A data structure for bicategories, with application to speeding up an approximation algorithm ⋮ Search problems: One, two or many rounds ⋮ The determinant of a tree's neighborhood matrix ⋮ On semi-\(P_ 4\)-sparse graphs ⋮ Generalized coloring for tree-like graphs ⋮ Minimum dispersion problems ⋮ Numerical database system based on a weighted search tree ⋮ Algebraic and numerical techniques for the computation of matrix determinants ⋮ Optimal channel allocation for several types of cellular radio networks ⋮ Hamiltonian cycles in circulant digraphs with two stripes ⋮ Edge-packing planar graphs by cyclic graphs ⋮ The algorithmic use of hypertree structure and maximum neighbourhood orderings ⋮ A real-time parallel application: The detection of gravitational waves by a network of heterogeneous workstations ⋮ ZAPROS-LM -- a method and system for ordering multiattribute alternatives ⋮ On the structure of graphs with few \(P_4\)s ⋮ Simple planar graph partition into three forests ⋮ A rewriting approach to satisfiability procedures. ⋮ Some properties and applications of the efficient Fisher score ⋮ Time-space tradeoffs for algebraic problems on general sequential machines ⋮ Permutation statistics and linear extensions of posets ⋮ Smoothness and factoring polynomials over finite fields ⋮ Radix sort on the hypercube ⋮ Lower bounds for arithmetic problems ⋮ On practical algorithms for accelerated matrix multiplication ⋮ Parallel priority queues ⋮ New clique and independent set algorithms for circle graphs ⋮ Expressing combinatorial optimization problems by linear programs ⋮ Strings, trees, and patterns ⋮ Parallel rectilinear shortest paths with rectangular obstacles ⋮ The complexity types of computable sets ⋮ Nash and correlated equilibria: Some complexity considerations ⋮ The complexity of some graph colouring problems ⋮ Hierarchy representations based on arithmetic coding for dynamic information protection systems ⋮ A solvable class of quadratic 0-1 programming ⋮ The point-to-point delivery and connection problems: Complexity and algorithms ⋮ On the problem of multiple mobile robots cluttering a workspace ⋮ Random pseudo-polynomial algorithms for some combinatorial programming problems ⋮ The traveling salesman problem: An overview of exact and approximate algorithms ⋮ A linear-time algorithm for isomorphism of a subclass of chordal graphs ⋮ Dynamic output-sensitive hidden surface removal for \(c\)-oriented polyhedra ⋮ Lower eigenvalue bounds for singular pencils of matrices ⋮ A graph-theoretic heuristic for designing loop-layout manufacturing systems ⋮ An approximation algorithm for the general routing problem ⋮ Optimal time bounds for some proximity problems in the plane ⋮ The parallel complexity of coarsest set partition problems ⋮ Sorting on PRAMs with reconfigurable buses ⋮ Matching theory -- a sampler: From Dénes König to the present ⋮ Solving the Euclidean bottleneck biconnected edge subgraph problem by 2- relative neighborhood graphs ⋮ Fault-detection in networks ⋮ A fast and efficient parallel algorithm for finding a satisfying truth assignment to a 2-CNF formula ⋮ A new upper bound on the complexity of the all pairs shortest path problem ⋮ Dense polynomial multiplication with reduced array manipulation overhead ⋮ An O\((nm)\) algorithm for a special case of the multimedian location problem on a tree ⋮ Degree constrained tree embedding into points in the plane ⋮ Fast algorithms for finding Hamiltonian paths and cycles in in-tournament digraphs ⋮ A minimum 3-connectivity augmentation of a graph ⋮ I/O- and CPU-optimal recognition of strongly connected components ⋮ An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees ⋮ Two fast simulations which imply some fast string matching and palindrome-recognition algorithms ⋮ On the equivalence, containment, and covering problems for the regular and context-free languages ⋮ Consistency in networks of relations ⋮ Augmented transition networks and their relation to tree transducers ⋮ Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics ⋮ The complexity of vector-products ⋮ Some elementary proofs of lower bounds in complexity theory ⋮ A note on pattern reproduction in tessellation structures ⋮ Algorithms for updating minimal spanning trees ⋮ Branching from the largest upper bound. Folklore and facts ⋮ Resource constrained scheduling as generalized bin packing ⋮ Palindrome recognition in real time by a multitape Turing machine ⋮ Concave cost minimization on networks ⋮ Universal classes of hash functions ⋮ On-line computation of convolutions ⋮ A recursive algorithm for matrix Padé approximants --- the divide-and- conquer approach ⋮ Parallel iterated bucket sort ⋮ An \(O(m\log n)\) algorithm for the max+sum spanning tree problem ⋮ LP relaxation of the two dimensional knapsack problem with box and GUB constraints ⋮ Total completion time minimization in two-machine job shops with unit-time operations ⋮ The partial sum criterion for Steiner trees in graphs and shortest paths ⋮ Minimal vertex separators of chordal graphs ⋮ Large computation of the maximum rank correlation estimator ⋮ Sentences over integral domains and their computational complexities ⋮ Decompositions to degree-constrained subgraphs are simply reducible to edge-colorings ⋮ Uncovering generalized-network structure in matrices ⋮ Generating the best \(K\) sequences in relocation problems ⋮ A note on the tour problems in two-terminal series-parallel graphs ⋮ Irreversibility problem in NL-class relations ⋮ On the Euclidean two paths problem ⋮ Displacement structure of pseudoinverses ⋮ Bin-packing by simulated annealing ⋮ Key generation of algebraic-code cryptosystems ⋮ Exact computation of Steiner minimal trees in the plane ⋮ Scaling algorithms for network problems ⋮ Exact methods for the knapsack problem and its generalizations ⋮ Irreducibility of multivariate polynomials ⋮ Algorithm partition and parallel recognition of general context-free languages using fixed-size VLSI architecture ⋮ Jebelean-Weber's algorithm without spurious factors ⋮ Simple DFS on the complement of a graph and on partially complemented digraphs ⋮ Domination analysis for minimum multiprocessor scheduling ⋮ Algorithmic aspects for multiple-choice hardware/software partitioning ⋮ On recognition of threshold tolerance graphs and their complements ⋮ Recognizing Cartesian products in linear time ⋮ A clustering algorithm based on maximal \(\varTheta\)-distant subtrees ⋮ A class of algorithms which require nonlinear time to maintain disjoint sets ⋮ Cut scheduling in the apparel industry ⋮ Algorithms for the edge-width of an embedded graph ⋮ Efficient inclusion testing for simple classes of unambiguous \(\omega \)-automata ⋮ On arithmetical algorithms over finite fields ⋮ Parallelism and fast solution of linear systems ⋮ q-hook length formulas for forests ⋮ The weighted perfect domination problem ⋮ Edge-disjoint paths in a grid bounded by two nested rectangles ⋮ A faster algorithm for the maximum weighted tardiness problem ⋮ On two dual classes of planar graphs ⋮ Computing the longest diagonal of a simple polygon ⋮ Hidden surface removal for rectangles ⋮ Computational complexity of sentences over fields ⋮ Time-varying Reeb graphs for continuous space-time data ⋮ The BOXEL framework for 2.5D data with applications to virtual drivethroughs and ray tracing ⋮ A linear-time algorithm for computing the intersection of all odd cycles in a graph ⋮ Reconstruction of a graph from 2-vicinities of its vertices ⋮ Algorithmic aspects of fuzzy control ⋮ On Simon's string searching algorithm ⋮ Tight comparison bounds for the string prefix-matching problem ⋮ Recognition of DFS trees: Sequential and parallel algorithms with refined verifications ⋮ Maintenance of 2- and 3-edge-connected components of graphs. I ⋮ Cycle structure of edge labelled graphs ⋮ Optimal vertex ranking of block graphs ⋮ On similarity of polynomial configurations ⋮ Bipartite bithreshold graphs ⋮ Integer sorting on a mesh-connected array of processors ⋮ Range-restricted mergeable priority queues ⋮ More concise representation of regular languages by automata and regular expressions ⋮ Centroidal trajectories and frames for chaotic dynamical systems ⋮ Parameterized graph cleaning problems ⋮ Scheduling linearly shortening jobs under precedence constraints ⋮ Consensus algorithms for the generation of all maximal bicliques ⋮ The problem of the moody chess players ⋮ Single machine group scheduling with resource dependent setup and processing times ⋮ Recursive formulation of the matrix Padé approximation in packed storage ⋮ Refined complexity analysis for heap operations ⋮ Modelisation dynamique litterale ⋮ Unary finite automata vs. arithmetic progressions ⋮ On finding fundamental cut sets ⋮ Finding all equilibria in games of strategic complements ⋮ Closed sets and translations of relation schemes ⋮ Building heaps in parallel ⋮ Reduction operations for constraint satisfaction ⋮ The continuous center set of a network ⋮ Optimal speeding up of parallel algorithms based upon the divide-and- conquer strategy ⋮ Exponential bounds for the running time of a selection algorithm ⋮ 3D-plex grammars ⋮ Improved polynomial algorithms for robust bottleneck problems with interval data ⋮ A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs ⋮ On-line computation of transitive closures of graphs ⋮ On legal path problems in digraphs ⋮ A low and a high hierarchy within NP ⋮ The complexity of restricted regular expressions and the synthesis problem for finite automata ⋮ On the complexity of chess ⋮ A priority queue for the all pairs shortest path problem ⋮ Edge-contraction problems ⋮ New trie data structures which support very fast search operations ⋮ The complexity of monadic recursion schemes: Exponential time bounds ⋮ Finding pseudoperipheral nodes in graphs ⋮ An n log n algorithm for determining the congruity of polyhedra ⋮ Comments on Detection of connectivity for regions represented by linear quadtrees ⋮ Multi-version concurrency control scheme for a database system ⋮ Algebraic approach to p-adic conversion of rational numbers ⋮ How evenly should one divide to conquer quickly? ⋮ Area-period tradeoffs for multiplication of rectangular matrices ⋮ Decomposition by clique separators ⋮ Cauchy-Toeplitz matrices and some applications ⋮ Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer ⋮ Factoring multivariate polynomials over finite fields ⋮ The optimality of balancing workloads in certain types of flexible manufacturing systems ⋮ A polynomial time algorithm for finding the prime factors of Cartesian- product graphs ⋮ On rectilinear link distance ⋮ Bit complexity of matrix products ⋮ Universal retrieval trees ⋮ A linear time algorithm for the maximum capacity path problem ⋮ The performance of multilective VLSI algorithms ⋮ An assignment algorithm with applications to integrated circuit layout ⋮ The maximum flow problem: A max-preflow approach ⋮ The k-neighbor domination problem ⋮ Independence results about context-free languages and lower bounds ⋮ The one-dimensional weighted Voronoi diagram ⋮ Exact balancing is not always good ⋮ Verifying nonrigidity ⋮ An efficient Dijkstra-like labeling method for computing shortest odd/even paths ⋮ New algorithms for the LCS problem ⋮ Parcours dans les graphes: Un outil pour l'algorithmique des ensembles ordonnés