Ratio Mathematica Volume 40, 2021, pp. 77-85 Recognizable Hexagonal Picture Languages and xyz Domino Tiles Anitha Pancratius * Rosini Babu Rajendran Pillai† Abstract In this paper we introduced xyz local hexagonal picture languages, where the usual notion of hexagonal tiles of size (2, 2, 2) are replaced by xyz dominoes, motivated by the studies of xyz domino systems. This new formalism is used for checking recognizability of hexag- onal pictures. It is noticed that non- regular hexagonal pictures can also be studied in the place of regular pictures. Recognizability of xyz local hexagonal picture were studied and the fact that every recogniz- able hexagonal p[icture languages can be obtained as a projection of xyz local hexagonal picture languages. Keywords: xyz domino system, Local hexagonal picture languages, recognizability of xyz domino system, mapping, hexagonal pictures, x domino, y domino, z domino.1 *Department of Mathematics, B J M Government College, Chavara; anitaben- son321@gmail.com, †Department of Mathematics, F M N College, Kollam;brosini@gmail.com 1Received on January 12th, 2021. Accepted on May 16th, 2021. Published on June 30th, 2021. doi:10.23755/rm.v40i1.610. ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors. This paper is published under the CC-BY licence agreement. 77 Anitha P, Rosini B. 1 Introduction A picture is used to understand things in a better way. Hexagonal pictures and tiles has got many significances. A lot of technologies are there to compute pictures with the help of computers. This resulted in the introduction of picture generating models. In [D.Giammarresi, 1992] Giammerresi et.al proposed the recognizability of picture languages. The languages in recognizable pictures were defined using tiling systems. Hexagonal pictures have got various uses particu- larly in picture processing and image analysis. Hexagonal arrays on triangular grid are viewed as two dimensional representation of three dimensional blocks and perceptual twins of pictures of a given set of blocks[KS, 2005]. Since late seventies, formal models to generate or recognize hexagonal pictures has been found in literature in the frame work of pattern recognition and image analysis. Recently searching for a new method for defining hexagonal pictures has moved towards the new definition for recognizable languages generated by hexag- onal pictures which inherits many properties from existing cases, in [Giammarresi, 1966],. Local and recognizable hexagonal picture languages in terms of hexago- nal tiling system were introduced and studied in [KS, 2005]. In [Dersanambika, 2004] K S Dersanambika et.al. define xyz- domino systems and charecterised hexagonal pictures using this. Subsequently hexagonal hv-local picture languages via hexagonal domino systems were introduced in the light of two dimensional domino system introduced by Latturex et.al [Latteurx, 1997]. Hexagonal arrays and hexagonal patterns are found in picture processing and image analysis [Der- sanambika, 2004]. It is very natural to consider hexagonal tiles on triangular grid, we require certain hexagonal tiles only to present in each hexagonal pictures of a hexagonal picture languages. This leads to recognizable hexagonal pictures and the hexag- onal tiling systems. The xyz domino tiling characterize the hexagonal picture languages. So we define xyz local hexagonal picture languages over the usual notion of a hexagonal picture of size (2, 2, 2) and proved that every recognizable hexagonal picture language can be obtained as some projection of these languages. 2 Recognizability of hexagonal pictures In this part we review the notions of formal language theory and some of the basic concepts on hexagonal pictures and hexagonal picture languages [Anitha, 2011]. Let Σ be a finite alphabet of symbols. A hexagonal picture p over Σ is a hexagonal array of symbols of Σ. The set of all hexagonal arrays of the alphabet Σ is denoted by Σ∗∗H . A hexagonal picture over the alphabet a, b, c d is shown in Figure 1. 78 Recognizable Hexagonal Picture Languages and xyz Domino Tiles a a b a b f c b c c a c d a a d c c a Figure 1 With respect to a triad of triangular axes (x, y, z) the co-ordinates of each element of the hexagonal picture in Figure 2(a) and Figure 2(b) respectively are given below [KS, 2005]. Figure2(a) Figure2(b) 79 Anitha P, Rosini B. If p ∈ Σ∗∗H , then p̂ is the hexagonal picture obtained by surrounding p with a special boundary # is called a bordered hexagonal picture which is shown in Figure 3. # # # # # a b c # # b b a b # # c a b c f # # d b e d # # c f a # # # # # Figure 3 Let l1(p) = l, l2(p) = m,l3(p) = n be the size of the hexagonal arrays. We writep = (l,m,n), the size of a picture. For a picture p of size (l,m,n) we have the bordered picture p̂ is of size(l + 1,m + 1,n + 1). Now we see the projections of hexagonal picture and projections of a lan- guage. Γ and Σ be two finite alphabets and π : Γ → Σ be a mapping, this mapping π is called a projection. A hexagonal tile is of the form as shown in Figure 4. Figure 4 Given a hexagonal picture p of size (l,m,n) we denote the set of hexagonal sub- picture of p of size (2, 2, 2) is called a hexagonal tile of size (2, 2, 2). Figure 4 denote a hexagonal tile of size (2, 2, 2). A hexagonal tiling system [Dersanambika, 2004] T is a 4-tuple (Σ, Γ,π,θ) where Σ and Γ are two finite set of symbols. π : Γ −→ Σ is a projection and θ is the set of hexagonal tiles over the alphabet Γ∪{#}. Definition 2.1. A hexagonal sub picture p̂′ is a picture which is a hexagonal sub array of the picture p̂. Given a hexagonal picture p̂ then Bl,m,n(p̂) denotes the set of hexagonal sub pictures of size l,m,n. For hexagonal pictures there are three types of concatenations namely type 1, type 2, and type 3 refer [Anitha, 2011]. A hexagonal picture language is rec- ognizable if there exist a local language L′ over an alphabet Σ and a mapping π : Γ −→ Σ such that L ⊆ π(L′). 80 Recognizable Hexagonal Picture Languages and xyz Domino Tiles 3 xyz local hexagonal picture languages In this section we introduce the notion of xyz local hexagonal picture lan- guages where the hexagonal tiles of size (2, 2, 2) are replaced by xyz dominos. Definition 3.1. L be a hexagonal picture language included in Σ∗∗H . L is said to be xyz local if there exist a set ∆ of x,y,z dominoes over Σ ∪{#} such that L = {q ∈ Σ∗∗H|T1,1,2(q) ∪T1,2,1(q) ∪T2,1,1(q) ⊆ ∆} Example 3.1. If we consider the hexagonal picture langauages L over the alpha- bet Σ = {0, 1} then all the hexagonal picture of can be obtained by the concate- nation of xy,yz,xz dominoes. Figure 5 The hexgonal picture so obtained is local as we can associate a set of xyz dominoes ∆ as follows which generates the whole picture. Here figure 6 show the picture generated by x dominoes, figure 7 shows the y dominoes, while figure 8 shows the z dominoes. Figure 6 Figure 7 Figure 8 81 Anitha P, Rosini B. Theorem 3.1. Let L ⊆ Σ∗∗H be a hexagonal picture language. If L is xyz local, then L is local. Proof. proof Let L ⊆ Σ∗∗H be a xyz local hexagonal picture language. For prov- ingt L is local, construct a local hexagonal picture language L′ and show that L = L′. We know that there exist a set ∆ of xyz dominoes over Σ ∪{#}(∆ ⊆ (Σ ⊆{#})(1,1,2) ∪ (Σ ⊆{#})(1,2,1) ∪ (Σ ⊆{#})(2,1,1)) such that L = {p ∈ Σ∗∗H|T1,1,2(p̂) ∪T1,2,1(p̂) ∪T2,1,1(p̂) ⊆ ∆}. We define the set of hexagonal pictures ∆ ′ , ∆ ′ = q ∈ (Σ ∪{#})(2,2,2)|T1,2,1(q̂) ∪T1,1,2(q̂) ∪T2,1,1(q̂) ⊆ ∆}. Let L′ = {p ∈ Σ∗∗H|T2,2,2(p̂) ⊆ ∆ ′ }. Clearly L′ is local. Now let p ∈ L′. Then T2,2,2(p̂) ⊆ ∆ ′ and T1,1,2(p̂) ⊆ T1,1,2(T2,2,2(p̂)) ⊆ T1,1,2(∆ ′ ) ⊆ ∆. Similarly T2,1,1(p̂) ⊆ ∆ and T1,2,1(p̂) ⊆ ∆. Hence p ∈ L. Therefore L′ ∈ L. To show that L ∈ L′. Let p ∈ L, let q ∈ L and a ∈ T2,2,2(q̂). Then T1,2,1(a) ⊆ T1,2,1(q̂) ⊆ ∆, T2,1,1(a) ⊆ T2,1,1(q̂) ⊆ ∆, and T1,1,2(a) ⊆ T1,1,2(q̂) ⊆ ∆. So a ∈ ∆′ , and q ∈ L′. Therefore L ∈ L′. Hence L = L′. That is if L is an xyz local hexagonal picture language then L is a local hexagonal picture language. Example 3.2. For instance, the hexagonal picture language defined above is local with, Figure 9 Theorem 3.2. Let L ⊆ Σ∗∗H be a hexagonal picture language. If L is local there exists a xyz local hexagonal picture language L′ over Σ ′ and a mapping π : Σ ′ → Σ such that L = π(L ′ ). Proof. We define an extended alphabet from Σ. We denote this alphabet E(Σ) = (Σ ∪{#})3,3,3. Now we define a mapping π, π : Σ∗∗H → E(Σ∗∗H ) 82 Recognizable Hexagonal Picture Languages and xyz Domino Tiles p → pE ∈ E(Σ∗∗H ). We define p and pE with same size and for all 1 6 i 6 l + 1, 1 6 j 6 m + 1, 1 6 k 6 n + 1 where (l,m,n) be the size ofp. Figure 10 It can be verified that every hexagonal tile of size (2, 2, 2) in pE where p ∈ Σ∗∗H appear in π(p) and vice versa. T2,2,2(p E) = ∪T2,2,2(a). If p ∈ Σ∗∗H where Σ = {0, 1} then Figure 11 where Figure 12 83 Anitha P, Rosini B. We also define a mapping φ from E(Σ∗∗H ) onto Σ∗∗H by π(a) = a(2, 2, 2) for a ∈ E(Σ). By using figure 10 it is clear that for all p ∈ Σ∗∗H we have p = φ(π(p)). Hence we conclude that L = π(L′) Theorem 3.3. Let L ∪ Σ∗∗H be a hexagonal picture language L is recognizable if and only if there exist a xyz local hexagonal picture language L′ over Σ ′ and a mapping π : Σ ′ → Σ such that L = π(L′). Proof. Let L be a recognizable hexagonal picture language over Σ. By defini- tion of recognizable picture languages we know that there exist a local hexagonal picture language L′ over an alphabet Σ ′ and a mapping π : Σ ′ → Σ such that L = π(L′). According to theorem 1 there exist a xyz local hexagonal picture language L′′ over an alphabet Σ ′′ and a mapping φ : Σ ′′ → Σ′ such that L′ = φ(L′′). From the above two results we get L = π(L′′) = π(φ(L′′)) where L′′ is xyz local. Now let L′ be a xyz local hexagonal picture language over Σ ′ , then π : Σ ′ → Σ be a mapping. Applying theorem 2 it follows that L′ is local and hence the hexagonal picture π(L′) is recognizable. 4 Conclusion xyz local recognizable hexagonal picture languages provides a new formalism of using xyz dominos instead of usual notation of hexagonal tile.We tried to prove that a hexagonal picture language L is recognizable and is the projection of a xyz local hexagonal picture language. In a similar way we can extend the various other properties of recognizable rectangular picture to recognizable hexagonal picture. References P. Anitha,K. Sujathakumari and K. S. Dersanambika. Hexagonal picture lan- guages and its recognizability Journal of Science, Technology and Manage- ment, 4, 2011. K. S. Dersanambika K. Krithivasan,C. Martin-Vide and K. G. Subramanian. Hexagonal Pattern Languages Lecture Notes on Computer Science, 3322, 2004. K. S. Dersanambika K. Krithivasan,C. Martin-Vide and K. G. Subramanian. Lo- cal and Recognizable Hexagonal Picture Languages International Journal of pattern recognition and Artificial Intelligence, 19(7), 2005. D. Giammarresi and A. Restivo. Two dimensional finite state recognizability Fun- damenta Informatica, 25(3,4), 1966. 84 Recognizable Hexagonal Picture Languages and xyz Domino Tiles D. Giammarresi and A. Restivo. Recognizable picture languages in parallel image processing World Scientific, 1992. M. Latteurx and D. Simplot. Recognizable picture languages and domino tiling Theoretical Computer Science,178, 1997. K. G. Subramanian. Hexagonal array grammars Computer Graphics and image processing,10, 1979. 85