  When their reading heads are allowed to move completely asynchronously,
finite-state automata with multiple tapes achieve a significant expressive
power, but also lose useful closure properties---closure under intersection, in
particular. This paper investigates to what extent it is still feasible to use
multi-tape automata as recognizer of polyadic predicates on words. On the
negative side, determining whether the intersection of asynchronous multi-tape
automata is expressible is not even semidecidable. On the positive side, we
present an algorithm that computes under-approximations of the intersection;
and discuss simple conditions under which it can construct complete
intersections. A prototype implementation and a few non-trivial examples
demonstrate the algorithm in practice.
