Array Grammars with Contextual Operations

Article type: Research Article

Authors: Subramanian, K.G. | Van, Do Long | Chandra, P. Helen | Quyen, Nghiem Do

Affiliations: School of Mathematical Sciences, Universiti Sains Malaysia, 11800 Penang, Malaysia. E-mail: kgsmani1948@yahoo.com | Institute of Mathematics, Hanoi, Vietnam. E-mail: dlvan@math.ac.vn | Department of Mathematics, Jayaraj Annapackiam College for Women Periyakulam, Theni, India

Abstract: In this paper, we consider a class of two-dimensional array grammars, called parallel contextual array grammars, that extend the contextual operations on strings to arrays in a naturalway and generate languages of pictures of rectangular arrays. Several classes of these array grammars and the resulting families of picture languages are considered. Necessary conditions for picture languages to be contained in these classes are obtained and the relations between these families are also established.

Keywords: Formal languages, Picture languages, Array grammars, Contextual grammars

Journal: Fundamenta Informaticae, vol. 83, no. 4, pp. 411-428, 2008