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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01442477
Contributor : Hal Ifip <>
Submitted on : Friday, January 20, 2017 - 4:09:28 PM
Last modification on : Thursday, February 7, 2019 - 5:46:47 PM
Long-term archiving on : Friday, April 21, 2017 - 3:43:52 PM

File

338243_1_En_19_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Véronique Terrier. Recognition of Linear-Slender Context-Free Languages by Real Time One-Way Cellular Automata. 21st Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2015, Turku, Finland. pp.251-262, ⟨10.1007/978-3-662-47221-7_19⟩. ⟨hal-01442477⟩

Share

Metrics

Record views

86

Files downloads

112