Open AccessA Note on Linear Time Simulation of Deterministic Two-Way Pushdown Automata
Author(s) -
Neil D. Jones
Publication year - 1977
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v6i75.6492
Subject(s) - backtracking , deterministic pushdown automaton , pushdown automaton , computer science , embedded pushdown automaton , algorithm , matching (statistics) , automaton , constant (computer programming) , time complexity , theoretical computer science , mathematics , nondeterministic finite automaton , automata theory , artificial intelligence , programming language , statistics , context free grammar , parsing , tree adjoining grammar
Cook has shown that any deterministic two-way pushdown automaton could be simulated by a uniform-cost random access machine in time O(n) for inputs of length n. The result was of interest because such a machine is a natural model for a variety of backtracking algorithms, particularly as used in pattern matching problems. The linear time result was surprising because of the fact that such machines may run as many as 2n steps before halting; similar problems with 'combinatorial explosions' are well known to occur in applications of backtracking. Cook's result inspired the development of a number of efficient pattern matching algorithms. However, it is impractical to use Cook's algorithm directly to do pattern matching, since it involves a large constant time factor and much storage. The purpose of this note is to present an alternate, simpler simulation algorithm which involves consideration only of the configurations actually reached by the automaton. It can be expected to run faster and use less storage (depending on the data structures used), thus bringing Cook's result a step closer to practical utility.