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.
Type de document :
Communication dans un congrès
Cezar Câmpeanu; Florin Manea; Jeffrey Shallit. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. Springer International Publishing, Lecture Notes in Computer Science, LNCS-9777, pp.98-110, 2016, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-41114-9_8〉
https://hal.inria.fr/hal-01633942
Contributeur : Hal Ifip
<>
Soumis le : lundi 13 novembre 2017 - 15:32:12
Dernière modification le : mercredi 6 décembre 2017 - 11:42:02
Document(s) archivé(s) le : mercredi 14 février 2018 - 15:03:56
Henning Fernau, Rudolf Freund, Rani Siromoney, K. Subramanian. Contextual Array Grammars with Matrix and Regular Control. Cezar Câmpeanu; Florin Manea; Jeffrey Shallit. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. Springer International Publishing, Lecture Notes in Computer Science, LNCS-9777, pp.98-110, 2016, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-41114-9_8〉. 〈hal-01633942〉
