Old automata problem
I like old problems that look withered. Sometimes, there is no reason to think of them because the world has moved on. Still, I like to visit them when I am on travel or commute or simply lost.
A 2DPDA is a deterministic pushdown automata with one stack and one 2-way head. Can we prove that no 2DPDA accepts the language L = {p#t | string p matches a substring in t; p and t may have wildcard characters that match any alphabet symbol}?
If L' is L where p and t do NOT have wildcards, it is the standard string matching problem and there is a quadratic time algorithm to accept L' by a 2DPDA. Cook (S. A. Cook, Linear-time simulation of deterministic two-way pushdown automata, Information Processing (IFIP) 71, C.V. Freiman, (ed.), NorthHolland, pp. 75--80, 1971.) proved that any language accepted by a 2DPDA can be accepted in linear time by a RAM, giving the first known linear time algorithm for string matching (this was a precursor to the KMP algorithm). No linear time algorithm is known for matching with wildcards.
A 2DPDA is a deterministic pushdown automata with one stack and one 2-way head. Can we prove that no 2DPDA accepts the language L = {p#t | string p matches a substring in t; p and t may have wildcard characters that match any alphabet symbol}?
If L' is L where p and t do NOT have wildcards, it is the standard string matching problem and there is a quadratic time algorithm to accept L' by a 2DPDA. Cook (S. A. Cook, Linear-time simulation of deterministic two-way pushdown automata, Information Processing (IFIP) 71, C.V. Freiman, (ed.), NorthHolland, pp. 75--80, 1971.) proved that any language accepted by a 2DPDA can be accepted in linear time by a RAM, giving the first known linear time algorithm for string matching (this was a precursor to the KMP algorithm). No linear time algorithm is known for matching with wildcards.
posted by metoo at 5:32 PM
2 Comments:
This sounds like a rather fundamental open problem... Do you know what the best results are? Is the problem hard even if there are wildcards just on one side (just pattern or just text)?
--mip
I do not know of any work that directly addressed this problem. Wildcard matching is at least as hard as Boolean Convolution even if there are wildcards just on one side. Perhaps people have studied Boolean Convolution in 2DPDA, but I don't know a reference.
Post a Comment
<< Home