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
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, 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., 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, Sorting weighted distances with applications to objective function evaluations in single facility location problems., (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, 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, Improved algorithms for computing determinants and resultants, Generating two-terminal directed acyclic graphs with a given complexity index by constraint logic programming, Constructing optimal binary decision trees is NP-complete, Approximation of the supply scheduling problem, Faster algorithms for computing power indices in weighted voting games, 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, 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, Minimization algorithms for sequential transducers, The design principles of a weighted finite-state transducer library, The complexity of the word problems for commutative semigroups and polynomial ideals, 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, Fringe analysis of synchronized parallel insertion algorithms in 2--3 trees., A note on resolving infeasibility in linear programs by constraint relaxation, 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, Fast Lagrange-Newton transformations, An existential locality theorem, Complementation of rational sets on scattered linear orderings of finite rank, Searching subsequences, Tetrahedrizing point sets in three dimensions, Petri nets, Horn programs, linear logic and vector games, Constructing normal bases in finite fields, An algorithm for generalized point location and its applications, The shifted number system for fast linear algebra on integer matrices, Improved algorithm for all pairs shortest paths, Unnamed Item, Efficient testing and matching of deterministic regular expressions, Parallel adaptive \(hp\)-refinement techniques for conservation laws, Generalizations of Checking Stack Automata: Characterizations and Hierarchies, The lex game and some applications, On-line construction of two-dimensional suffix trees, Factoring polynomials over finite fields: A survey, An efficient sparse adaptation of the polytope method over \(\mathbb F_q\) and a record-high binary bivariate factorisation, A Gröbner free alternative for polynomial system solving, Complexity of universality and related problems for partially ordered NFAs, Fast algorithms for the Sylvester equation \(AX-XB^{T}=C\), Fast algorithms for multivariate interpolation and evaluation at special points, A nonasymptotic lower time bound for a strictly bounded second-order arithmetic, Fast parallel and serial multidimensional approximate array matching, Parallel algorithms for red--black trees, Subset construction complexity for homogeneous automata, position automata and ZPC-structures, Fast matrix decomposition in \(\mathbb F_2\), Pushdown automata with counters, Generalizations of suffix arrays to multi-dimensional matrices., The time-precision tradeoff problem on on-line probabilistic Turing machines, Transductions of dags and trees, Optimal systolic array algorithms for tensor product, On the number of ANDs versus the number of ORs in monotone Boolean circuits, More efficient on-the-fly LTL verification with Tarjan's algorithm, On Floyd and Rivest's SELECT algorithm, 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
Cites Work
