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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Choffrut, C., Čulík II, K.: On real-time cellular automata and trellis automata. Acta Informatica 21(4), 393–407 (1984)
Čulík II, K.: Variations of the firing squad problem and applications. Information Processing Letters 30(3), 152–157 (1989)
Čulík II, K., Gruska, J., Salomaa, A.: Systolic trellis automata. I, II. International Journal Computer Mathematics 16, 3–22 (1984)
Čulík II, K., Gruska, J., Salomaa, A.: Systolic trellis automata: Stability, decidability and complexity. Information and Control 71(3), 218–230 (1986)
Dyer, C.R.: One-way bounded cellular automata. Information and Control 44(3), 261–281 (1980)
Ginsburg, S., Spanier, E.H.: Bounded algol-like languages. Transactions of the American Mathematical Society 113, 333–368 (1964)
Ilie, L., Rozenberg, G., Salomaa, A.: A characterization of poly-slender context-free languages. Theoretical Informatics and Applications 34(1), 77–86 (2000)
Latteux, M., Thierrin, G.: On bounded context-free languages. Elektronische Informationsverarbeitung und Kybernetik 20(1), 3–8 (1984)
Naji, M.: Ambiguity of context-free languages as a function of the word length. FB Informatik. Goethe Universität, Frankfurt am Main (1998)
Okhotin, A.: On the equivalence of linear conjunctive grammars and trellis automata. RAIRO Informatique Thorique et Applications 38(1), 69–88 (2004)
Okhotin, A.: Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages. In: Černá, I., Gyimóthy, T., Hromkovič, J., Jefferey, K., Králović, R., Vukolić, M., Wolf, S. (eds.) SOFSEM 2011. LNCS, vol. 6543, pp. 431–443. Springer, Heidelberg (2011)
Terrier, V.: On real time one-way cellular array. Theoretical Computer Science 141(1–2), 331–335 (1995)
Terrier, V.: Language not recognizable in real time by one-way cellular automata. Theoretical Computer Science 156(1–2), 281–287 (1996)
Terrier, V.: Closure properties of cellular automata. Theoretical Computer Science 352(1–3), 97–107 (2006)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 IFIP International Federation for Information Processing
About this paper
Cite this paper
Terrier, V. (2015). Recognition of Linear-Slender Context-Free Languages by Real Time One-Way Cellular Automata. In: Kari, J. (eds) Cellular Automata and Discrete Complex Systems. AUTOMATA 2015. Lecture Notes in Computer Science(), vol 9099. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47221-7_19
Download citation
DOI: https://doi.org/10.1007/978-3-662-47221-7_19
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47220-0
Online ISBN: 978-3-662-47221-7
eBook Packages: Computer ScienceComputer Science (R0)