Publication:4091421
From MaRDI portal
zbMath0326.68005MaRDI QIDQ4091421
Jeffrey D. Ullman, John E. Hopcrofts, A. V. Aho
Publication date: 1974
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68-02: Research exposition (monographs, survey articles) pertaining to computer science
68N01: General topics in the theory of software
68W99: Algorithms in computer science
Related Items
On the impact of stratification on the complexity of nonmonotonic reasoning, Fast parallel Lyndon factorization with applications, SEARCHING ALGORITHMS IMPLEMENTED ON PROBABILISTIC SYSTOLIC ARRAYS, Optimizing Long‐term Hydro‐power Production Using Markov Decision Processes, The Hamilton circuit problem on grids, Tight Ω(nlgn) lower bound for finding a longest increasing subsequence, Characterizing switch-setting problems∗, Discrete Weighted Transforms and Large-Integer Arithmetic, The Monte Carlo Complexity of Fredholm Integral Equations, Subquadratic-time factoring of polynomials over finite fields, Detecting perfect powers in essentially linear time, On Shuffle Ideals, Computing Division Polynomials, A Reliability and Performance Model For Static Data Flow Machines, On a New Factorization Algorithm for Polynomials Over Finite Fields, The Variance Location Problem on a Network with Continuously distributed demand, PROCESSOR-TIME-OPTIMAL SYSTOLIC ARRAYS, Vowel-consonant addressing mode on hashing for English letter-oriented keys, Efficient algorithms for computing the $L_2$-discrepancy, On the Size of One-way Quantum Finite Automata with Periodic Behaviors, AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗, A QUEUEING MODELLING APPROACH TO CLUSTERED HETEROGENEOUS DISCRETE EVENT DYNAMIC SYSTEMS, Minimized Thompson NFA, Simulation of circuits of functional elements by the universal Turing machine, On-line computations of the ideal lattice of posets, Rational transductions and complexity of counting problems, Mineurs d'arbres avec racines, Generalized Bottleneck Problems∗, A fast average case algorithm for lyndon decomposition, Two-way automata and length-preserving homomorphisms, Efficient reductions of picture words, An approach to parallel algorithm design, A large pair of twin primes, Sorting on Single-Channel Wireless Sensor Networks, M-Heap: A Modified Heap Data Structure, GOLOMB RULERS AND DIFFERENCE SETS FOR SUCCINCT QUANTUM AUTOMATA, On the complexity of calculation of differentials and gradients, THEORETICAL ISSUES OF SEARCHING AERIAL PHOTOGRAPHS: A BIRD'S EYE VIEW, Complexity of general continuous minimization problems: a survey, Persistency in combinatorial optimization problems on matroids, One-unambiguous regular languages, One-unambiguous regular languages, An optimal algorithm for the construction of the system dependence graph, An optimal algorithm for computing the max-min transitive closure of a fuzzy similarity matrix, Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\), Compression using efficient multicasting, Window-accumulated subsequence matching problem is linear, The computational complexity of recognizing permutation functions, Pac-learning non-recursive Prolog clauses, Minimizing phylogenetic number to find good evolutionary trees, Graph properties checkable in linear time in the number of vertices, Precise interprocedural dataflow analysis with applications to constant propagation, On quasilinear-time complexity theory, Linear bounds for on-line Steiner problems, An O(n \text{log} n) implementation of the standard method for minimizing n-state finite automata, Context-free recognition via shortest paths computation: a version of Valiant's algorithm, Using multiset discrimination to solve language processing problems without hashing, Efficient algorithms for shortest distance queries on special classes of polygons, Using quadratic programming to solve high multiplicity scheduling problems on parallel machines, Approximation algorithms for the bandwidth minimization problem for a large class of trees, Mathematical aspects of concept analysis, An application of program unification to priority queue vectorization, A stubborn attack on state explosion, More efficient bottom-up multi-pattern matching in trees, Fast recognition of deterministic cfl's with a smaller number of processors, Shortest path computations in source-deplanarized graphs, On the complexity of recursive path orderings, Another variation on the common subexpression problem, Some computational problems in linear algebra as hard as matrix multiplication, Non-deterministic exponential time has two-prover interactive protocols, A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio, Tiling a simply connected figure with bars of length 2 or 3, Techniques for exploiting structure in matrix formulae of the sparse resultant, Almost optimal sublinear time parallel recognition algorithms for three subclasses of context free languages, A network penalty method, Processor-time optimal parallel algorithms for digitized images on mesh- connected processor arrays, Testing planar pictures for isomorphism in linear time, The isomorphism problem for classes of graphs closed under contraction, Optimal geometric algorithms for digitized images on fixed-size linear arrays and scan-line arrays, Efficient algorithms for divisive hierarchical clustering with the diameter criterion, On the degree of ambiguity of finite automata, Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays, Self complementary topologies and preorders, Inverting a Vandermonde matrix in minimum parallel time, Planar orientations with low out-degree and compaction of adjacency matrices, Uniform random generation of expressions respecting algebraic identities, The image of weighted combinatorial problems, Discrete convolution with modulo operations, Divided \(k-d\) trees, Cycle-free partial orders and chordal comparability graphs, Temporal constraint networks, Further comments on the subtree isomorphism for ordered trees, Iterated stack automata and complexity classes, Optimal canonization of all substrings of a string, Oracle branching programs and Logspace versus \(P^*\), Equivalence of models for polynomial learnability, On finding the minimum bandwidth of interval graphs, Shortest path algorithms: A computational study with the C programming language, Optimal placement of identical resources in a tree, On fast multiplication of polynomials over arbitrary algebras, A linear algorithm for bisecting a polygon, Testing the optimality of alphabetic trees, A model classifying algorithms as inherently sequential with applications to graph searching, Minimisation of acyclic deterministic automata in linear time, New scaling algorithms for the assignment and minimum mean cycle problems, The use of Knuth-Bendix methods to solve the word problem in automatic groups, The functional dimension of inductive definitions, Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time, An \(O(n\log n)\) algorithm for computing the link center of a simple polygon, The complexity of computing a best response automaton in repeated games with mixed strategies, Search performance of double-linked coalesced hashing can not exceed bucketing, A framework for 1-D compaction with forbidden region avoidance, There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees, On the continuous quadratic knapsack problem, Canonical representations of partial 2- and 3-trees, An extension of the multi-path algorithm for finding Hamilton cycles, An in-depth empirical investigation of non-greedy approaches for the minimum spanning tree problem, The most vital edges with respect to the number of spanning trees in two- terminal series-parallel graphs, Fast detection and display of symmetry in outerplanar graphs, Random list permutations in place, Communication for alternating machines, An optimal lower bound on the number of variables for graph identification, Reasoning about qualitative temporal information, Polynomial division with a remainder by means of evaluation and interpolation, A parallel algorithm for exact solution of linear equations via congruence technique, A hierarchical algorithm for making sparse matrices sparser, The slab dividing approach to solve the Euclidean \(P\)-center problem, Maximum \(k\)-covering of weighted transitive graphs with applications, String matching problems over free partially commutative monoids, Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under \(l_ \infty\)-distance, On finding common subtrees, The set of types of a finitely generated variety, Distances in orientations of graphs, On the implementation of Strassen's fast multiplication algorithm, NP-complete scheduling problems, Priority queues with update and finding minimum spanning trees, The NP-completeness of the bandwidth minimization problem, Boolesche Minimalpolynome und Überdeckungsprobleme, The analysis of Quicksort programs, A hashing method for fast set operations, On batch scheduling of jobs with stochastic service times and cost structures on a single server, Polynomial and abstract subrecursive classes, An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications, Representation of structured events and efficient procedures for their recognition, Planning a time-minimal motion among moving obstacles, Extracting maximal information about sets of minimum cuts, Regular sequence operations and their use in database queries, Periodicities on trees, Scheduling multiprocessor tasks with chain constraints, Formalization of the class of problems solvable by a nondeterministic Turing machine, Scheduling inverse trees under the communication model of the LogP-machine, Deterministic generalized automata, Computational implementation of Fujishige's graph realizability algorithm, Rank estimators for monotonic index models, The line index and minimum cut of weighted graphs, A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources, Sensitivity analysis of the economic lot-sizing problem, A new optimal algorithm for backbone topology design in communications networks, Finding extremal sets in less than quadratic time, Reduction of OBDDs in linear time, Locating service centers with precedence constraints, Finding all maximal efficient faces in multiobjective linear programming, Efficient enumeration of the vertices of polyhedra associated with network LP's, Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs, Self-testing/correcting with applications to numerical problems, A new look at Euclid's second proposition, Computability, complexity and economics, Machine calculations in Weyl groups, Determination of the efficient set in multiobjective linear programming, Cord-slope form of Taylor's expansion in univariate global optimization, Incremental construction of 2-structures, Edge crossings in drawings of bipartite graphs, Deriving fold/unfold transformations of logic programs using extended OLDT-based abstract interpretation, Speeding up dynamic transitive closure for bounded degree graphs, On minimizing the \(\forall\)-\(\neg\) degree of a connective-free formula, On the lengths of values in a finite transducer, Dynamic programming and graph optimization problems, Invariance properties of RAMs and linear time, Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach, On computation complexity problems concerning relation algebras, A fast and simple algorithm for the bottleneck biconnected spanning subgraph problem, Dynamic factorization in large-scale optimization, Data structures for two-edge connectivity in planar graphs, A term equality problem equivalent to graph isomorphism, Automatically generating abstractions for planning, The uniform memory hierarchy model of computation, Unit-cost pointers versus logarithmic-cost addresses, An optimal sublinear time parallel algorithm for some dynamic programming problems, A constant update time finger search tree, Multiple-type, two-dimensional bin packing problems: Applications and algorithms, Inversion of 2D cellular automata: Some complexity results, Finite-valued distance automata, Exponential upper and lower bounds for the order of a regular language, Scheduling project activities in a distributed environment, Periodic sets of integers, The path-partition problem in block graphs, Algorithms constructing a representive vector criterion for a binary preference relation, A locally optimized reordering algorithm and its application to a parallel sparse linear system solver, A logic for reasoning about time and reliability, Parallel integer sorting using small operations, A new variant of the \(A^*\)-algorithm which closes a node at most once., \(k\) best cuts for circular-arc graphs, Question-asking strategies for Horn clause systems, On the exponent of all pairs shortest path problem, A data structure for arc insertion and regular path finding, The input/output complexity of transitive closure, Analysis of discrete data: Rerandomization methods and complexity, Batch RSA, Batch Diffie-Hellman key agreement systems, Representations of group automata, Sorting strings and constructing digital search trees in parallel, A vectorized algorithm for cluster formation in the Swendsen-Wang dynamics, The monadic second-order logic of graphs. X: Linear orderings, The zooming method: A recursive approach to time-space efficient string-matching, The bases of weighted graphs, Recognition of Robinsonian dissimilarities, Efficient learning with virtual threshold gates, Algorithms, complexity and discreteness criteria in \(PSL(2,C)\), Lower bounds for polynomial evaluation and interpolation problems, Graph theory and the amateur cryptographer, On the complexity of specification morphisms, Multiple sequence comparison -- a peptide matching approach, From regular expressions to DFA's using compressed NFA's, An O(n log n) algorithm for the generalized birthday problem, Finding a shortest vector in a two-dimensional lattice modulo m, Completeness results for graph isomorphism., On computation of the greatest common divisor of several polynomials over a finite field., A linear algorithm for the Hamiltonian completion number of the line graph of a cactus., A stochastically quasi-optimal search algorithm for the maximum of the simple random walk, The bottleneck independent domination on the classes of bipartite graphs and block graphs., Sorting and doubling techniques for set partitioning and automata minimization problems, Characterization of Glushkov automata, An optimal algorithm for solving the 1-median problem on weighted 4-cactus graphs, Algorithms for exponentiation in finite fields, On the isomorphism of expressions, Re-describing an algorithm by Hopcroft, On point-duration networks for temporal reasoning, An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs, A linear algorithm for integer programming in the plane, Group scheduling with controllable setup and processing times: minimizing total weighted completion time, A note on the factorization method of Niederreiter, Representing graph families with edge grammars, A new approach to fast polynomial interpolation and multipoint evaluation, Lower bounds for arithmetic networks, On a signal processing algorithms based class of linear codes, Exploiting special structure in a primal-dual path-following algorithm, On determining non-isotopic configurations of points on a circle, Three characterizations of non-binary correlation-immune and resilient functions, A spanning-tree algorithm for constructing streams in pipelines, Complexity analysis of algorithms by recognition of their classification properties, Generative languages, codes and parallel processing, Fonction sommatoire de la fonction de Möbius 1. Majorations expérimentales, Categories, relations and dynamic programming, Recursive generation of locally complete tests, An information technology for efficiency analysis of recursive algorithms using standard complexity recurrences, Orthogonal descent to a convex set in a linear manifold, Sorting, linear time and the satisfiability problem, Computing with pipelined block transfer, Comparison of strings belonging to the same family, Two-pattern strings. I: A recognition algorithm, Drawing series parallel digraphs symmetrically, A linear time algorithm for the bottleneck biconnected spanning subgraph problem, Real-time properties of indirect recursive procedures, Fast computation of canonical lifts of elliptic curves and its application to point counting., Online scheduling with partial job values: does timesharing or randomization help?, Dynamic nested brackets, On iterating linear transformations over recognizable sets of integers, Linkless symmetric drawings of series parallel digraphs, Employing symmetry reductions in model checking, New primal and dual matching heuristics, Point set pattern matching in \(d\)-dimensions, Fully dynamic biconnectivity in graphs, Isomorphism of chordal (6, 3) graphs, Using geometry to solve the transportation problem in the plane, Characterizing and recognizing the visibility graph of a funnel-shaped polygon, Fast generation of prime numbers and secure public-key cryptographic parameters., On the look-ahead problem in lexical analysis, An optimal parallel algorithm for planar cycle separators, An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications, A fast algorithm for expansion over spherical harmonics, Execution of simple similarity predicates in the DSM method for automatic generation of hypotheses, New algorithms for linear \(k\)-matroid intersection and matroid \(k\)-parity problems, The parallel complexity of growth models, Using topological sweep to extract the boundaries of regions in maps represented by region quadtrees, Searching among intervals and compact routing tables, Data structures and algorithms for the string statistics problem, A fast algorithm for a class of bottleneck problems, Determining bar-representability for ordered weighted graphs, Constrained matroidal bottleneck problems, A loop-free algorithm for generating the linear extensions of a poset, A linear time algorithm for maximum matchings in convex, bipartite graphs, Decremental 2- and 3-connectivity on planar graphs, Covering a string, The \(Multi\)-SAT algorithm, Best second order bounds for two-terminal network reliability with dependent edge failures, Inner-core and outer-core functions of partially defined Boolean functions, Linear-time LUP decomposition of forest-like matrices, Fourier acceleration of iterative processes in disordered systems., On \(k\)-positive satisfiability problem, Balancing sparse matrices for computing eigenvalues, Gradable logical values for knowledge representation, Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order, Computing Frobenius maps and factoring polynomials, Fast exponentiation using the truncation operation, The searching over separators strategy to solve some NP-hard problems in subexponential time, Splitting a configuration in a simplex, Explicit factorization of \(x^{2^ k}+1\) over \(F_ p\) with prime \(p\equiv 3\bmod 4\), Selection on rectangular meshes with multiple broadcasting, Application of the dual active set algorithm to quadratic network optimization, Tabu search for a class of scheduling problems, On certain Hamiltonian inner triangulations, Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces, Powers of matrices over distributive lattices -- a review, Inversion of circulant matrices over $\mathbf{Z}_m$, Computing the prefix of an automaton, Sorting using heap structure, WORDS GUARANTEEING MINIMUM IMAGE, On the rapid computation of various polylogarithmic constants, SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS, A model of sequential computation with Pipelined access to memory, Objects in relational database schemes with functional, inclusion, and exclusion dependencies, Random Generation for Finitely Ambiguous Context-free Languages, Polynomial factorization over ${\mathbb F}_2$, Commutative images of rational languages and the Abelian kernel of a monoid, The Length of Elements in Free Solvable Groups, On Computing Factors of Cyclotomic Polynomials, Minmax linear knapsack problem with grouped variables and gub, On scaling linear programs—some experimental results, Unnamed Item, HIERARCHICAL SYSTEM CONCEPTS FOR SIMULATION OF HIGH AUTONOMY SYSTEMS, The convex hull of a set of convex polygons, An set refinement algorithm with applications, Mutual derivability of operations in program algebras. II, Temporal Structures, A minimization method for boolean functions, Algorithms for minimization of finite acyclic automata and pattern matching in terms, Weak equivalence of automata, Generalized kolmogorov complexity and other dual complexity measures, Decidable, polynomial-time, and np-complete cases of the isotone bipartite graph problem, Iterative methods of program analysis: Equalities and inequalities, A parallel algorithm for the minimization of finite state automata, On double-one matrices and double-zero matrices, Modeling and simulation of a nonhomogeneous poisson process having cyclic behavior, A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere, Distance automata having large finite distance or finite ambiguity, Computer algebra in probability and statistics, Applications of graph theory in computer systems, On efficiently computing the product of two binary relations, A polynomial-time algorithm for optimal clustering in a special class of {0, l} -matrices, Factoring high-degree polynomials over $\mathbf F_2$ with Niederreiter's algorithm on the IBM SP2
