nt.number theory - A decision problem concerning polynomial rings

Let $alpha in overline{mathbb{Q}}$ be such that all $f_i$ have coefficients in $mathbb{Q}(alpha)$ and $k in mathbb{N}$ such that the $f_i$ are in
$mathbb{Q}(alpha)[y_1, ldots, y_k]$. Then the ideal the generated by the $f_i$ in this ring corresponds to an ideal $J$ in $mathbb{Q}[x,y_1, ldots, y_k]$ which is generated by lifts of the $f_i$ together with the minimal polynomial $f$ of $alpha.$
Now clearly a neccessary condition for your problem is that $J cap mathbb{Q}[y_1 ldots, y_k]neq {0}.$ This can be checked algorithmically by computing a Groebner basis with respect to an elimination term ordering, c.f. e.g. Kreuzer/Robbiano, Computational Commutative Algebra.

For a complete solution to the original question, you are not interested in the ideal generated by the polynomials but in the subalgebra they generate. Again, sometimes it"s possible to compute the gadgets corresponding to Groebner bases for ideals; these then are called SAGBI bases, which you would need to compute with respect to an elimination term ordering. In contrast to Groebner bases, these do not neccessarily exist, though.

To summarise: SAGBI basis is the notion you're looking for, if I'm not mistaken.