3
$\begingroup$

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?

$\endgroup$

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.