# Forbidden Sequence Dynamic Programming

Given a finite set $$\Omega$$, I have the following problem. Say there is a list of forbidden subsequences $$F \subset \Omega \cup \Omega^2 \cup \Omega^3 \dots \Omega^\infty$$, while we do not know the contents of list before hand, we can make a query about any sequence $$S \in \Omega^i$$ to see if $$\exists f \in F, f \subseteq S$$. (here $$f \subseteq S$$ means that $$f$$ is an uninterrupted "substring" of $$S$$) I want to construct a sequence $$S \in \Omega^n$$ such that $$f \not \subseteq S, \forall f \in F$$.

The approach I thought would be best is to use dynamic programming. We iteratively construct valid sets $$V_k := \{S \in \Omega_k: f \not \subset S ,\forall f \in F, |f|< k\}$$, by requiring each subsequence of $$s \in V_1 \cup \dots V_{k-1}, \forall s \subsetneq S$$, and then remove all $$S \in F$$ with queries. My question is, what's the most efficient way to construct $$V_k$$? One simple way would be to take $$V_{k-1}$$ and then try adding each element in $$\Omega$$ at the end, and then do some extra queries, but is there some better way?

Additionally, are there elegant ways to use incomplete valid sets $$I_k \subseteq V_k$$, where if $$I_{k+1} := \{S \in \Omega^{k+1} \setminus F: s \in I^1 \cup \dots I^k, \forall s \subsetneq S\}$$ is empty, we can try to retroactively expand everything without mostly starting from scratch?