Sunday, February 19, 2006

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.

4 Comments:

Anonymous Anonymous said...

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

6:22 PM  
Blogger metoo said...

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.

10:25 PM  
Blogger luccy said...

A whole array of anti-obesity pills and medicines are available in the market that helps you to trigger off successful weight loss but the weight loss diet pill Xenical is somewhat different as it prevents around 30% of the fat you take from being absorbed in your system. This further leads to less fat accumulation and ultimately weight loss becomes a reality. For more details on Xenical, visit the website http://www.weight-loss-truths.com

3:48 AM  
Blogger Kelvin said...

Here is the equation that you can choose while selecting your daily food. About 50-55% carbohydrates, 30-35% protein, and the rest can be fat. Something close to this is healthy. Just remember, carbs are your biggest source of energy; they are not all bad. The carbs that are unhealthy are the ones that come from processed foods and simple sugars. Try to eat more whole wheat grain foods, legumes, and live food such as fresh fruits and vegetables. http://www.phentermine-effects.com

1:16 AM  

Post a Comment

<< Home