Polynomial Algorithms for Deterministic Pushdown Automata

Daniel J. Rosenkrantz, Harry B. Hunt IiiSIAM Journal on Computing 1978 · OpenReview

Abstract

An algorithm is presented for converting a deterministic pushdown automaton (dpda) of size n into an equivalent dpda that always halts. The dpda produced is of size $O(n)$. The algorithm operates in linear time on a random access machine (but may require the allocation of $O(n^2 )$ storage), and in time $O(n^2 )$ on a multi-tape Turing machine. Related results on polynomial time algorithms for dpda equivalence problems and for two-way pushdown automata language recognition problems are discussed.
BibTeX
@article{rosenkrantz1978polynomial,
  author = {Daniel J. Rosenkrantz and Harry B. Hunt III},
  title = {{Polynomial Algorithms for Deterministic Pushdown Automata}},
  journal = {SIAM Journal on Computing},
  year = {1978},
  url = {https://openreview.net/forum?id=gGIrLsvaZm},
}

Loading related content...

Figure