push-down automaton

(redirected from Pushdown automaton)
Also found in: Wikipedia.

push-down automaton

[′pu̇sh‚dau̇n ȯ′täm·ə‚tän]
(computer science)
A nondeterministic, finite automaton with an auxiliary tape having the form of a push-down storage.
Mentioned in ?
References in periodicals archive ?
2] (defined below) are context free by designing non deterministic pushdown automaton that accepts them.
R] is context free by designing a non deterministic finite pushdown automaton that accepts it.
A non deterministic pushdown automaton or NPDA is a 7-tuple M = (Q, [SIGMA], [?
We have presented a new method to implement a pushdown automaton based on DNA molecules and restriction enzymes.
Biomolecular Pushdown Automaton Based on the DNA Computing.
20) for a proof of the theorem stating that "A language is context free if and only if some pushdown automaton recognizes it".
2000] construct a pushdown automaton for regular tree-parsing which can be used for code generation with dynamic cost computation [Gantait 1996].
The algorithm effectively solves the problem of optimal regular tree-pattern-matching by constructing a pushdown automaton that performs matching in linear time, and precomputes costs.
Third, using the same basic machinery, we show that the recognition problem for deterministic context-free languages can be solved quickly on a deterministic auxiliary pushdown automaton having random access to its input tape, a log n space work tape, and pushdown store of small maximum height.
Allow the owner, parent, and sibling functions above to be computable by a deterministic log space auxiliary pushdown automaton that runs in polynomial time.
We know that, say, CREW-PRAM time O(log n) can be simulated by a logarithmic space deterministic auxiliary pushdown automaton that runs in time [n.
Mogensen showed that a certain variant of a two-way deterministic pushdown automaton (a so-called "WORM-2DPDA") can be simulated in linear time on a RAM computer (even though the WORM2DPDA itself may perform an exponential number of steps).