In this paper we prove that the problem of deciding whether a determin
istic rational relation is star-free is recursively solvable, although
the same problem for any rational relation is undecidable. We also pr
ove that a rational relation is star-free if and only if it is aperiod
ic and deterministic.