On the computational power of pushdown automata
From MaRDI portal
Publication:2542990
DOI10.1016/S0022-0000(70)80004-6zbMath0207.01701OpenAlexW2044283261MaRDI QIDQ2542990
A. V. Aho, John E. Hopcrofts, Jeffrey D. Ullman
Publication date: 1970
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(70)80004-6
Related Items (only showing first 100 items - show all)
Efficient algorithms for robustness in resource allocation and scheduling problems ⋮ Compatibility of unrooted phylogenetic trees is FPT ⋮ System structure: stability and controllability ⋮ Efficient string matching with k mismatches ⋮ A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers ⋮ 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 ⋮ The incremental maintenance of a depth-first-search tree in directed acyclic graphs ⋮ A tight bound for approximating the square root ⋮ Efficient stream distribution algorithm for heterogeneous multimedia multicast with link capacity constraint ⋮ K-M-P string matching revisited ⋮ A coarse-grained multicomputer algorithm for the detection of repetitions ⋮ Path-based depth-first search for strong and biconnected components ⋮ An optimal \(O(N^{2})\) algorithm for computing the min-transitive closure of a weighted graph ⋮ Computing a ham-sandwich cut in two dimensions ⋮ Algorithms for near solutions to polynomial equations ⋮ Even faster integer multiplication ⋮ Polynomial division and its computational complexity ⋮ An O(m n) algorithm for regular set-covering problems ⋮ Scheduling with semaphore constraints ⋮ On the cost of searching signature trees ⋮ 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 ⋮ String-matching with OBDDs ⋮ A multiprocessor architecture for solving nonlinear partial differential equations ⋮ 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 ⋮ 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 ⋮ Linear time analysis of properties of conflict-free and general Petri nets ⋮ Complexity of dimension three and some related edge-covering characteristics of graphs ⋮ The optimal all-partial-sums algorithm in commutative semigroups and its applications for image thresholding segmentation ⋮ On evaluating strategies for the computation of DWBA integrals ⋮ The derivational complexity of string rewriting systems ⋮ Dynamic maintenance of directed hypergraphs ⋮ Communication complexity of PRAMs ⋮ A complexity theory of efficient parallel algorithms ⋮ Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers ⋮ 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. ⋮ \(k\)-abelian pattern matching ⋮ 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 ⋮ Alternating space is closed under complement and other simulations for sublogarithmic space ⋮ Computability of recurrence equations ⋮ Efficient detection of quasiperiodicities in strings ⋮ Complexity of algorithm and operations on trees ⋮ The unpredictable deviousness of models ⋮ Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm ⋮ Simultaneous modular reduction and Kronecker substitution for small finite fields ⋮ Anonymous message communications with user hierarchy in a multicast system ⋮ A note on detecting simple redundancies in linear systems ⋮ Efficient heuristic algorithms for path-based hardware/software partitioning ⋮ Minimizing the density of terminal assignments in layout design ⋮ Fast computation of divided differences and parallel Hermite interpolation ⋮ On the parameterized complexity of associative and commutative unification ⋮ Open problems in computational linear algebra ⋮ On limits on the computational power of data-accumulating algorithms ⋮ Optimal state-space lumping in Markov chains ⋮ Simple algorithms for approximating all roots of a polynomial with real roots ⋮ The complexity of equivalence for commutative rings ⋮ Cost analysis of object-oriented bytecode programs ⋮ Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation ⋮ An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem ⋮ Two flow network simplification algorithms ⋮ Upper bounds for sorting integers on random access machines ⋮ Computational experience with minimum spanning tree algorithms ⋮ 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 ⋮ 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 ⋮ 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 ⋮ An approach to the subgraph homeomorphism problem ⋮ Multiplication is the easiest nontrivial arithmetic function ⋮ On efficient recognition of transductions and relations ⋮ Limitedness theorem on finite automata with distance functions: An algebraic proof ⋮ Computing in general Abelian groups is hard ⋮ Quasi-gcd computations ⋮ Complexity results on the conjugacy problem for monoids ⋮ Molecular dynamics on vector computers
Cites Work
This page was built for publication: On the computational power of pushdown automata
