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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.