HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Contextual Array Grammars with Matrix and Regular Control

Abstract : We investigate the computational power of d-dimensional contextual array grammars with matrix control and regular control languages. For $$d\ge 2$$, d-dimensional contextual array grammars are less powerful than matrix contextual array grammars, which themselves are less powerful than contextual array grammars with regular control languages. Yet in the 1-dimensional case, for a one-letter alphabet, the family of 1-dimensional array languages generated by contextual array grammars with regular control languages coincides with the family of regular 1-dimensional array languages, whereas for alphabets with more than one letter, we obtain the array images of the linear languages.
Document type :
Conference papers
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Monday, November 13, 2017 - 3:32:12 PM
Last modification on : Wednesday, November 3, 2021 - 4:18:26 AM
Long-term archiving on: : Wednesday, February 14, 2018 - 3:03:56 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Henning Fernau, Rudolf Freund, Rani Siromoney, K. Subramanian. Contextual Array Grammars with Matrix and Regular Control. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. pp.98-110, ⟨10.1007/978-3-319-41114-9_8⟩. ⟨hal-01633942⟩



Record views


Files downloads