Two-dimensional array grammars in palindromic languages

Abstract

In this paper, we put forward models that generate two-dimensional palindromic languages with array-rewriting rules. The rewriting rules are of either regular or context-free type with terminals being arrays. The derivation lengths are managed by the array concatenation conditions. These grammars give rise to an extensive variety of palindromic pictures. Different hierarchies that exist between the classes defined are demonstrated. The closure properties have also been evaluated. Applications of these models have been explored by generating a few patterns of kolams.

Keywords

• array grammars
• palindromic arrays
• picture languages
• kolams
• formal languages