Polynomial Algorithms for Deterministic Pushdown Automata
Lists
Only you see this
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...