Recognition of Linear-Slender Context-Free Languages by Real Time One-Way Cellular Automata
Résumé
A linear-slender context-free language is a context-free language whose number of words of length is linear in . Its structure has been finely characterized in a work of Ilie, Rozenberg and Salomaa. Thanks to this characterization, we show that every linear-slender context-free language is recognizable by a real time one-way cellular automaton.
Domaines
Informatique [cs]
Origine : Fichiers produits par l'(les) auteur(s)
