New answers tagged

0

There is an algorithm that checks, for every two regular languages $L_1,L_2$ given as DFAs, whether $L_1 \subseteq L_2$. The idea is to construct a DFA for $L_1 \setminus L_2$ using the product construction, and then to check emptiness, by checking whether some accepting state is reachable from the initial state. If your regular expressions are "TCS-...


0

Just to answer with some ideas. If you have too many dimensions, you can use the Johnson–Lindenstrauss lemma to reduce the dimensions while keeping distances approximately the same (some $\epsilon$ away from original distances). You can find a 3-approximation for the point in $B$ that is farthest away from any point in $A$ (pick any $b' \in B$, then find an $...


Top 50 recent answers are included