Non-Isometric Contextual Array Grammars and the Role of Regular Control and Local Selectors

• Autorzy: Fernau H. , Siromoney R. , Freund R. , Subramanian K. G.

Identyfikatory

DOI

10.3233/FI-2017-1582

• Języki publikacji: EN

Abstrakty

EN

We consider the external variant of non-isometric d-dimensional contextual array grammars with regular control together with local selectors allowing for controlling how d-dimensional arrays are evolving by adjoining rectangular (d-1)-dimensional arrays. In the 1-dimensional case, the computational power of these non-isometric contextual array grammars with regular control and local selectors equals the computational power of isometric contextual array grammars with regular control. The string images of the languages of 1-dimensional arrays generated by these contextual array grammars exactly yield the linear languages. In the more-dimensional case, non-isometric d-dimensional contextual array grammars with regular control and local selectors can simulate the computations of (d - 1)-dimensional array grammars or Turing machines. Hence, for example, the emptiness problem for non-isometric d-dimensional contextual array grammars with regular control and local selectors for d > 1 is undecidable. We also compare the computational power of all variants of non-isometric d-dimensional contextual array grammars that we introduce to each other.

Słowa kluczowe

EN

array languages; contextual grammars; isometric versus non-isometric variants

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 155, nr 1/2
• Strony: 209--232
• Opis fizyczny: Bibliogr. 29 poz.

Twórcy

autor

Fernau H.

• FB 4 - Abteilung Informatikwissenschaften, Universität Trier, D-54296 Trier, Germany

autor

Siromoney R.

• Chennai Mathematical Institute, Kelambakkam 603103, India

autor

Freund R.

• Institut für Computersprachen, Technische Universität Wien, A-1040 Wien, Austria

autor

Subramanian K. G.

• Department of Mathematics and Computer Science, Faculty of Science, Liverpool Hope University, Liverpool, L16 9JD, Great Britain

Bibliografia

• [1] Marcus S. Contextual grammars. Rev. Roum. Math. Pures Appl., 1969;14:1525–1534.
• [2] Rozenberg G, Salomaa A (eds.). Handbook of Formal Languages (3 volumes). Springer, 1997. ISBN:978-3-642-63859-6, 978-3-642-59126-6.
• [3] Salomaa A. Formal Languages. Academic Press, 1973.
• [4] Pǎun Gh, Nguyen XM. On the inner contextual grammars. Revue Roumaine de Mathématiques Pures et Appliquées, 1980;25:641–651.
• [5] Ehrenfeucht A, Pǎun Gh, Rozenberg G. Contextual grammars and formal languages. In: Rozenberg G, Salomaa A (eds.), Handbook of Formal Languages, Volume II, pp. 237–293. Springer, 1997. ISBN:3-540-60648-3.
• [6] Pǎun Gh. Marcus contextual grammar. Studies in Linguistics and Philosophy. Dordrecht: Kluwer Academic Publishers, 1997. doi:10.1007/978-94-015-8969-7.
• [7] Rosenfeld A. Picture Languages. Academic Press, 1979. ISBN:978-0-12-597340-3.
• [8] Rosenfeld A, Siromoney R. Picture Languages – A Survey. Languages of Design, 1993;1:229–245. URL http://dl.acm.org/citation.cfm?id=198440.198442.
• [9] Giammarresi D, Restivo A. Two-dimensional languages. In: Rozenberg G, Salomaa A (eds.), Handbook of Formal Languages, Volume III, pp. 215–267. Springer, 1997. doi:10.1007/978-3-642-59126-6_4.
• [10] Pradella M, Cherubini A, Crespi-Reghizzi S. A unifying approach to picture grammars. Information and Computation, 2011;209(9):1246–1267. URL https://doi.org/10.1016/j.ic.2011.07.001.
• [11] Fernau H, Freund R. Bounded parallelism in array grammars used for character recognition. In: Perner P, Wang PP, Rosenfeld A (eds.), Advances in Structural and Syntactical Pattern Recognition (Proceedings of the SSPR’96), volume 1121 of LNCS. Springer, 1996 pp. 40–49. doi:10.1007/3-540-61577-6_5.
• [12] Freund R, Pǎun Gh, Rozenberg G. Chapter 8: Contextual array grammars. In: Subramanian KG, Rangarajan K, Mukund M (eds.), Formal Models, Languages and Applications, volume 66 of Series in Machine Perception and Articial Intelligence, pp. 112–136. World Scientific, 2007.
• [13] Fernau H, Freund R, Siromoney R, Subramanian KG. Contextual Array Grammars with Matrix and Regular Control. In: Câmpeanu C, Manea F, Shallit J (eds.), Descriptional Complexity of Formal Systems: 18th IFIP WG 1.2 International Conference, DCFS 2016, Bucharest, Romania, July 5-8, 2016. Proceedings, pp. 98–110. Springer International Publishing, 2016. doi:10.1007/978-3-319-41114-9_8.
• [14] Krithivasan K, Balan M, Rama R. Array Contextual Grammars. In: Martín-Vide and Pǎun [29], 2000 pp. 154–168.
• [15] Bottoni P, Mauri G, Mussio P. Bidimensional Contextual Grammars. In: Martín-Vide and Pǎun [29], 2000 pp. 25–45.
• [16] Rama R, Smitha TA. Some Results on Array Contextual Grammars. In: Siromoney R, Nakamura A, Narasimhan R, Nivat M, Rosenfeld A, Subramanian KG (eds.), Proceedings of the Sixth International Workshop on Parallel Image Processing and Analysis—Theory and Applications—IWPIPA. Indira Gandhi Centre for Atomic Research (IGCAR) and Madras Christian College, 1999 pp. 226–246.
• [17] Fernau H, Freund R, Siromoney R, Subramanian KG. Regulated Contextual Array Grammars. Annals of the University of Bucharest (Seria Informatica), 2015;LXII(3):63–78.
• [18] Freund R. Control mechanisms on #-context-free array grammars. In: Mathematical Aspects of Natural and Formal Languages. World Scientific, 1994 pp. 97–137. ISBN:9-8102-1914-8.
• [19] Wang PP. Some new results on isotonic array grammars. Information Processing Letters, 1980;10(3):129–131. URL https://doi.org/10.1016/0020-0190(80)90063-0.
• [20] Freund R, Kogler M, Oswald M. A General Framework for Regulated Rewriting Based on the Applicability of Rules. In: Kelemen J, Kelemenová A (eds.), Computation, Cooperation, and Life, volume 6610 of LNCS, Springer 2011 pp. 35–53.
• [21] Nagy B. On a hierarchy of 5'→3' sensing Watson-Crick finite automata languages. Journal of Logic and Computation, 2013;23(4):855–872. URL https://doi.org/10.1093/logcom/exr049.
• [22] Fernau H. Even linear simple matrix languages: formal language properties and grammatical inference. Theoretical Computer Science, 2002;289(1):425–489. URL https://doi.org/10.1016/S0304-3975(01)00313-9.
• [23] Subramanian KG. A note on regular controlled apical growth filamentous systems. International Journal of Computer and Information Sciences, 1985;14(4):235–242. doi:10.1007/BF00997022.
• [24] Takada Y. A hierarchy of language families learnable by regular language learning. Information and Computation, 1995;123(1):138–145. URL https://doi.org/10.1006/inco.1995.1163.
• [25] Fernau H, Paramasivan M, Schmid M, Thomas D. Scanning Pictures the Boustrophedon Way. In: Barneva R, Bhattacharya B, Brimkov V (eds.), International Workshop on Combinatorial Image Analysis IWCIA, volume 9448 of LNCS. Springer, 2015 pp. 202–216. doi:10.1007/978-3-319-26145-4_15.
• [26] Krithivasan K, Siromoney R. Array automata and operations on array languages. International Journal of Computer Mathematics, 1974;4(A):3–40. URL http://dx.doi.org/10.1080/00207167408803078.
• [27] Siromoney G, Siromoney R, Krithivasan K. Picture Languages with Array Rewriting Rules. Information and Control (now Information and Computation), 1973;22(5):447–470. URL https://doi.org/10.1016/S0019-9958(73)90573-1.
• [28] Fernau H, Freund R, Siromoney R, Subramanian KG. Non-isometric Contextual Array Grammars with Regular Control and Local Selectors. In: Durand-Lose J, Nagy B (eds.), Machines, Computations, and Universality MCU, volume 9288 of LNCS. Springer, 2015 pp. 61–78. doi:10.1007/978-3-319-23111-2_5.
• [29] Martín-Vide C, Pǎun Gh (eds.). Recent Topics in Mathematical and Computational Linguistics. Editura Academiei Romˆane, 2000. ISBN:973-27-0770-4.