Recognition of poly-slender context-free languages by trellis automata

A poly-slender context-free language is a context-free language whose number of words of length n is polynomially bounded. Its structure has been thoroughly characterized by Ilie, Rozenberg and Salomaa. Thanks to this characterization, we show that every poly-slender context-free language is recognizable by a trellis automaton, if the languages of words with as many a as b and at most a constant number of alternations between a and b are recognizable by trellis automata. Then we construct a family of trellis automata that recognizes such languages.