  Two languages are separable by a piecewise testable language if and only if
there exists no infinite tower between them. An infinite tower is an infinite
sequence of strings alternating between the two languages such that every
string is a subsequence (scattered substring) of all the strings that follow.
For regular languages represented by nondeterministic finite automata, the
existence of an infinite tower is decidable in polynomial time. In this paper,
we investigate the complexity of a particular method to compute a piecewise
testable separator. We show that it is closely related to the height of maximal
finite towers, and provide the upper and lower bounds with respect to the size
of the given nondeterministic automata. Specifically, we show that the upper
bound is polynomial with respect to the number of states with the cardinality
of the alphabet in the exponent. Concerning the lower bound, we show that
towers of exponential height with respect to the cardinality of the alphabet
exist. Since these towers mostly turn out to be sequences of prefixes, we also
provide a comparison with towers of prefixes.
