Abstract:

No abstract in the paper.  See e.g. Zentralblatt review 768.05007. However,  the last sentence of the review should read correctly:

"The main result is that, in the case of forbidden patterns f over two symbols, the maximum length is of order n if and only if the forbidden pattern f has no subsequence of the form ababa."

For f with more than two symbols this equivalence does not hold (e.g. for f=abcbadadbcd; viz the next paper in the list). To characterize general forbidden patterns f for which we have an O(n) bound to the maximum length is an open problem.