Let $L, K \subseteq X^{\ast}$ be languages, then we set $$ K^{-1}L := \{ u \in X^{\ast} \mid vu \in L \mbox{ for some } v \in K \} = \bigcup_{v\in K} v^{-1}L $$ with $u^{-1}L := \{ w \in X^{\ast} \mid uw \in L \}$ for $u \in X^{\ast}$. Then in this paper (on page 25 and 26) it is shown for regular $L$ and arbitrary $K$, the set $K^{-1}L$ is regular. Their proof goes like this, if $\mathcal A = (Q, T, I, F)$ is an automaton for $L$, let $I'$ be the set of states of $\mathcal A$ which are accessible from an initial state of $\mathcal A$ following a path labeled by a word of $K$, $$ I' := \{ q \in Q \mid \exists i \in I, \exists u \in K : \mbox{the automaton has a transition from $i$ to $q$ by $u$} \}. $$ Then $\mathcal A' = (Q, T, I', F)$ recognizes $K^{-1}L$. $\square$
After that they remark:
The proof is not effective: we may not be able to construct the set of states $I'$ associated with $K$. However, if $K$ is rational too, then $I'$ is effectively constructible.
What do they mean by "effective", do they mean constructible in finite time? If so, I think it is enough to suppose that $K$ is decidable (i.e. for each $w \in X^{\ast}$ we know in a finite amount of time if $w \in K$ or $w \notin K$). As for reachability in a finite automaton, it is enough to inspect the words of length $\le |Q|$ where $Q$ denotes the states of the automaton, and if $K$ is decidable we can test whether each such word is in $K$ or not, hence this procedure finishes in a finite amount of time. Is this what they want to say? And if so, why they restrict $K$ to be rational, if decidable would be enough? Or do they have some specific automata construction involving $K$ in mind?
Yes, "effective" means something like the construction can be carried out in finite time.
But this does not mean that it is enough that $K$ is decidable. Consider for example that we could let $$ K=\{\mathtt{a}^n\mid n\text{ is a perfect number}\} $$ and $L=(\mathtt{aa})^* $.
It is easy enough to specify a way to decide $K$, but that does not make it any easier to figure out whether the state of $L$ that corresponds to odd $n$s is reached by a word in $K$ or not.
This example also shows that it can well be necessary to check words in $K$ that are much longer than the number of states in an automaton for $L$.