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

Authors :: Véronique Terrier
Equipe AMACC - Laboratoire GREYC - UMR6072
Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC)
Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN)
Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN)
Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN)
Normandie Université (NU)
Source :: Theoretical Computer Science, Theoretical Computer Science, Elsevier, 2017, 692, pp.1-24. ⟨10.1016/j.tcs.2017.05.041⟩
Publication Year :: 2017
Publisher :: Elsevier BV, 2017.
Abstract: 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.