Recognition of Linear-Slender Context-Free Languages by Real Time One-Way Cellular Automata

Abstract : A linear-slender context-free language is a context-free language whose number of words of length n is linear in n . 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.
Type de document :
Communication dans un congrès
Jarkko Kari. 21st Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2015, Turku, Finland. Lecture Notes in Computer Science, LNCS-9099, pp.251-262, 2015, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-662-47221-7_19〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01442477
Contributeur : Hal Ifip <>
Soumis le : vendredi 20 janvier 2017 - 16:09:28
Dernière modification le : mardi 26 septembre 2017 - 01:32:18
Document(s) archivé(s) le : vendredi 21 avril 2017 - 15:43:52

Fichier

338243_1_En_19_Chapter.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Véronique Terrier. Recognition of Linear-Slender Context-Free Languages by Real Time One-Way Cellular Automata. Jarkko Kari. 21st Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2015, Turku, Finland. Lecture Notes in Computer Science, LNCS-9099, pp.251-262, 2015, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-662-47221-7_19〉. 〈hal-01442477〉

Partager

Métriques

Consultations de la notice

52

Téléchargements de fichiers

5