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.
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〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

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

Fichier

 Accès restreint
Fichier visible le : 2019-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

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〉

Partager

Métriques

Consultations de la notice

50