On the computational power of pushdown automata

DOI10.1016/S0022-0000(70)80004-6zbMath0207.01701MaRDI QIDQ2542990

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

Publication date: 1970

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

68Q45: Formal languages and automata

Related Items

Efficient simplicity testing of automata, Probabilistic modeling of data structures on words. A reply to Professor Andersson's letter, A problem that is easier to solve on the unit-cost algebraic RAM, Two \(P\)-complete problems in the theory of the reals, Efficient CRCW-PRAM algorithms for universal substring searching, Constructing optimal binary decision trees is NP-complete, Relative complexity of checking and evaluating, Realizing Boolean functions on disjoint sets of variables, On finding all unilaterally connected components of a digraph, The polynomial-time hierarchy, Implementing dictionaries using binary trees of very small height, An O(N) algorithm for finding periodicity of a sequence using hash coding, Preserving order in a forest in less than logarithmic time and linear space, Complete sets and the polynomial-time hierarchy, The Min-Max Spanning Tree Problem and some extensions, The DT-polynomial approach to discrete time-varying network flow problems, The expected linearity of a simple equivalence algorithm, Cycle detection in critical path networks, A linear-time algorithm for finding all feedback vertices, Optimum domination in weighted trees, A fast convex hull algorithm, A note on the optimal inverter problem, Deadline scheduling of tasks with ready times and resource constraints, Arithmetical hierarchy and complexity of computation, Three efficient algorithms for counting problems, The typed lambda-calculus is not elementary recursive, Optimal circular arc representations: Properties, recognition, and construction, A new approach to the word and conjugacy problems in the braid groups, Sign determination in residue number systems, Using fast matrix multiplication to find basic solutions, On the disjunctive set problem, Model checking and boolean graphs, An efficient parallel algorithm for the single function coarsest partition problem, Fast algorithms for the maximum convolution problem, Algebraic improvements of numerical algorithms: Interpolation and economization of Taylor series, Linear-time optimal augmentation for componentwise bipartite-completeness of graphs, Dividing strategies for the optimization of a test suite, Optimal location of facilities on a network with an unreliable node or link, Uniform random generation of words of rational languages, Unification of kinded infinite trees, When can we sort in \(o(n\log n)\) time?, Parallel computation of polynomial GCD and some related parallel computations over abstract fields, Intuitionistic formal theories with realizability in subrecursive classes, An efficient membership-query algorithm for learning DNF with respect to the uniform distribution, A theory of discontinuities in physical system models, On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs, Perfect hashing, Algorithmic graph embeddings, Maximum tree-packing in time \(O(n^{5/2})\), Optimal insertion in deterministic DAWGs, Generalizations of suffix arrays to multi-dimensional matrices., The complexity of bisimilarity-checking for one-counter processes., Sorting weighted distances with applications to objective function evaluations in single facility location problems., Minimization algorithms for sequential transducers, The design principles of a weighted finite-state transducer library, Randomized algorithms over finite fields for the exact parity base problem., Algorithms for fast convolutions on motion groups, Multi-subsequence searching, Repetitive perhaps, but certainly not boring, Easy weighted majority games, On asymptotically optimal methods of prediction and adaptive coding for Markov sources, Computing transformation semigroups, Approximate solutions of polynomial equations., Predicting zero coefficients in formal power series computations., Short vectors of planar lattices via continued fractions, Algorithms for transitive closure, Improved algorithms for computing determinants and resultants, Generating two-terminal directed acyclic graphs with a given complexity index by constraint logic programming, Approximation of the supply scheduling problem, Faster algorithms for computing power indices in weighted voting games, Manipulating derivation forests by scheduling techniques, Transducers and repetitions, Extraction and verification of programs by analysis of formal proofs, Classical and quantum function reconstruction via character evaluation, The complexity of the word problems for commutative semigroups and polynomial ideals, The time-precision tradeoff problem on on-line probabilistic Turing machines, On the number of ANDs versus the number of ORs in monotone Boolean circuits, Signature files and signature trees., A simplified correctness proof for a well-known algorithm computing strongly connected components., A speed-up for the commute between subword trees and DAWGs., Minimizing subsequential transducers: a survey., Efficient splitting and merging algorithms for order decomposable problems., Extension of Hoshen-Kopelman algorithm to non-lattice environments, Fringe analysis of synchronized parallel insertion algorithms in 2--3 trees., Watermelon uniform random generation with applications, A strong induction scheme that leads to polynomially computable realizations, The complexity of first-order and monadic second-order logic revisited, An existential locality theorem, Petri nets, Horn programs, linear logic and vector games, Parallel adaptive \(hp\)-refinement techniques for conservation laws, Fast parallel and serial multidimensional approximate array matching, A note on resolving infeasibility in linear programs by constraint relaxation, Fast Lagrange-Newton transformations, Complementation of rational sets on scattered linear orderings of finite rank, The shifted number system for fast linear algebra on integer matrices, The lex game and some applications, An efficient sparse adaptation of the polytope method over \(\mathbb F_q\) and a record-high binary bivariate factorisation, A nonasymptotic lower time bound for a strictly bounded second-order arithmetic, Pushdown automata with counters, Optimal systolic array algorithms for tensor product, A note on detecting simple redundancies in linear systems, Minimizing the density of terminal assignments in layout design, Fast computation of divided differences and parallel Hermite interpolation, String-matching with OBDDs, The aggregation and cancellation techniques as a practical tool for faster matrix multiplication, A note on the complexity of approximative evaluation of polynomials, The complexity of computing the permanent, How the character comparison order shapes the shift function of on-line pattern matching algorithms, On the acceptance power of regular languages, Resolving all deadlocks in distributed systems, A simple sub-quadratic algorithm for computing the subset partial order, A theory of even functionals and their algorithmic applications, An algebraic characterization of frontier testable tree languages, A grid embedding into the star graph for image analysis solutions, Sparse interpolation of symmetric polynomials, Computability of recurrence equations, Efficient detection of quasiperiodicities in strings, Complexity of algorithm and operations on trees, Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm, Anonymous message communications with user hierarchy in a multicast system, Simple algorithms for approximating all roots of a polynomial with real roots, The complexity of equivalence for commutative rings, Upper bounds for sorting integers on random access machines, The complexity of monadic recursion schemes: executability problems, nesting depth, and applications, A parallel-design distributed-implementation (PDDI) general-purpose computer, Efficient inference control for range SUM queries, A fast algorithm for the linear multiple-choice knapsack problem, The techniques of trilinear aggregating and the recent progress in the asymptotic acceleration of matrix operations, Limitedness theorem on finite automata with distance functions: An algebraic proof, Efficient algorithms for robustness in resource allocation and scheduling problems, Compatibility of unrooted phylogenetic trees is FPT, Dynamic maintenance of directed hypergraphs, Communication complexity of PRAMs, A complexity theory of efficient parallel algorithms, An O\((n\log n)\) version of the Averbakh-Berman algorithm for the robust median of a tree, An efficient automata approach to some problems on context-free grammars., The unpredictable deviousness of models, Open problems in computational linear algebra, On limits on the computational power of data-accumulating algorithms, Computational experience with minimum spanning tree algorithms, Embeddings of binary trees in lines, An algorithm for identifying Morishima and anti-Morishima matrices and balanced digraphs, Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra, An approach to the subgraph homeomorphism problem, Multiplication is the easiest nontrivial arithmetic function, On efficient recognition of transductions and relations, Computing in general Abelian groups is hard, Quasi-gcd computations, Complexity results on the conjugacy problem for monoids, Molecular dynamics on vector computers, System structure: stability and controllability, Efficient string matching with k mismatches, Richard Bellman's contributions to computer science, On the construction of parallel computers from various basis of Boolean functions, The principle of optimality in the design of efficient algorithms, Computing a ham-sandwich cut in two dimensions, Polynomial division and its computational complexity, An O(m n) algorithm for regular set-covering problems, Scheduling with semaphore constraints, Amortized efficiency of a path retrieval data structure, Parameter-reduction of higher level grammars, Complexity of parallel matrix computations, Recognizing max-flow min-cut path matrices, A fast algorithm for the discrete Laplace transformation, A multiprocessor architecture for solving nonlinear partial differential equations, Worst-case analysis of the set-union problem with extended backtracking, Total domination in block graphs, Univariate polynomial factorization over finite fields, The suffix tree of a tree and minimizing sequential transducers, Data representation and computational complexity, Fast verification, testing, and generation of large primes, Uniform data encodings, Complexity of Boolean algebras, Complexity of dimension three and some related edge-covering characteristics of graphs, On evaluating strategies for the computation of DWBA integrals, Non deterministic polynomial optimization problems and their approximations, Some elements of a Galois theory of the structure and complexity of the tree automorphism problem, General approximation algorithms for some arithmetical combinatorial problems, Partitioning a graph in \(O(|A|\log_ 2|V|)\), On the complexity of edge labelings for trees, An algorithm for matrix symmetrization, A graph theoretic approach to switching function minimization, Scheduling subject to nonrenewable-resource constraints, (g//0,g//1,\dots ,g//k)-trees and unary OL systems, On the complexity of the one-terminal network design problem, A simple algorithm to detect balance in signed graphs, The complexity of computing metric distances between partitions, R-domination of block graphs, A pointer-free data structure for merging heaps and min-max heaps, On-line computation of minimal and maximal length paths, Polynomial-time algorithms for testing strong isomorphism and computing the automorphism group of \(R\)-strongly connected automata, On the evaluation of the eigenvalues of a banded Toeplitz block matrix, AUTOMATE, a computing package for automata and finite semigroups, An optimal algorithm for \(2 \times{} n\) bottleneck transportation problems, A time-efficient, linar-space local similarity algorithm, Dynamic programming with convexity, concavity and sparsity, Two recognizable string-matching problems over free partially commutative monoids, Minimisation of acyclic deterministic automata in linear time, Parallel solution of Toeplitzlike linear systems, Partial memoization for obtaining linear time behavior of a 2DPDA, Transductions of dags and trees, On-line construction of two-dimensional suffix trees, Factoring polynomials over finite fields: A survey, A Gröbner free alternative for polynomial system solving, Fast algorithms for the Sylvester equation \(AX-XB^{T}=C\), Parallel algorithms for red--black trees, Subset construction complexity for homogeneous automata, position automata and ZPC-structures, Generalizations of suffix arrays to multi-dimensional matrices., More efficient on-the-fly LTL verification with Tarjan's algorithm, On Floyd and Rivest's SELECT algorithm, Searching subsequences, Tetrahedrizing point sets in three dimensions, Constructing normal bases in finite fields, An algorithm for generalized point location and its applications, Unnamed Item

Cites Work