Recognition of Linear-Slender Context-Free Languages by Real Time One-Way Cellular Automata - Cellular Automata and Discrete Complex Systems
Conference Papers Year : 2015

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

Véronique Terrier
Université de Caen Normandie
CV

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.

Domains

Computer Science [cs]
Fichier principal
Vignette du fichier
338243_1_En_19_Chapter.pdf (373.73 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Hal Ifip  : Connect in order to contact the contributor

https://inria.hal.science/hal-01442477

Submitted on : Friday, January 20, 2017-4:09:28 PM

Last modification on : Tuesday, October 19, 2021-11:34:30 PM

Long-term archiving on : Friday, April 21, 2017-3:43:52 PM

Download

Dates and versions

hal-01442477 , version 1 (20-01-2017)

Licence

Attribution

Identifiers

Cite

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⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

IFIP-LNCS IFIP COMUE-NORMANDIE IFIP-TC IFIP-TC1 IFIP-LNCS-9099 IFIP-AUTOMATA UNICAEN
101 View
116 Download

Altmetric

Share

More