Show that checking if there exists word not containg patterns from list is in $PSPACE$

Question

There are given:

• alphabet $Σ$ with some symbols $a,b$.
• list of forbidden patterns

Result: Is there exists word of form $a\Sigma^*b$ such that it doesn't contains (as subword) any of word from list (list contains many words, expressed by patterns). Show that this problem is in $PSPACE$.

Example to better understand patterns: $bbaaacb$ contains a word $a??c$, but $aacba$ doesn't contain $a??c$, where $?$ is some special symbol in $\Sigma$

So patterns are like words with holes (?)

My approach is follwing:
Let $k$ will be max length among all patterns. There is no sense to consider longer words than $k$ because if exists word longer than $k$ such that it contain none of words from forbidden list then also exists word of length $k$.

So, using the fact that $PSPACE = NPSPACE$ we can guess word of length $i=1...k$ and check if it contains subword from forbidden list. Matching is easy to do in $NPSPACE$.

I am not sure about corectness of using nondeterminism. What do you think ?

Answer 1

i think you are in the right direction, i will try to expand your answer a bit. first we want to prove that a problem is in PSPACE, which means there exists a TM that solves the problem with a polynomial space tape.

let M be a NTM that receives $w=<Σ,list>$ and does the following algorithm:

1) guess word of length $i=1...k$ given the $Σ$.this can be done in polynomial space depending on our input, since $O(k)=O(|w|)$ space.

2) check if there exists a pattern in the list which matches any of the strings of the word. this phase needs describing how exactly it can to be done, but it can certainly be done in polynomial space of $|w|$. hint: use 2 special characters to check each sub-string at a time.

and now since $PSPACE=NPSPACE$ (as you mentioned) ,if there exists a NTM that solves the problem in Polynomial Space tape we can conclude the problem is in $PSPACE$ and your solution was in a good direction.