Certain Comparison Results on Parallel Contextual Array Insertion Deletion Grammar

Abstract

Parallel Contextual array insertion and deletion grammars (PCAIDG) are the recently introduced formalism for generating rectangular array languages using insertion and deletion operations and parallel contextual mappings. PCAIDG strictly include Tiling System (TS) of Giammaresi and Restivo.  On the other hand, a context free class of grammar model named, Tile rewriting grammars (TRG) is also introduced in recent time for rectangular picture generation by amalgamating isometric rewriting rules with the Tiling System. TRG is proved to be more powerful than TS and array grammars by Siromoney and Prusa. In this work, we compare PCAIDG with TRG to understand the expressiveness in depth and form a hierarchy of these classes of grammars.