September 21, 2017, Thursday


Jump to: navigation, search

Seminar July 16, 2008, 13.45

Context Free Grammars for Picture Languages: Tile Rewriting Grammars

Anthonath Roslin Sagaya Mary

Wednesday July 16, 2008, DISCo U14, T014, 13:45

The talk will be about Tile Rewriting Grammars (TRG) introduced in [1]. TRG are rewriting rules that changes a homogeneous rectangular subpicture with specified tiles into an isometric one tile. The idea of this grammar is to extend the string case of Context free languages to 2D languages. The contents of [1], [2] will be discussed, constituting of a normal form to the grammar and the closure properties of the language, various comparisons of the class of languages like that of TRG, non-recursive TRG, TRG suitably defined as corner grammars with the 2D tiling systems.


[1] A. Cherubini, S. Crespi Reghizzi, M. Pradella, P. San Pietro, Picture languages: Tiling system versus Tile rewriting grammars, Theoretical Computer Science 356(1-2), (2006) 90 - 103.

[2] S. Crespi Reghizzi, M. Pradella, Tile rewriting grammars and picture languages, Theoretical Computer Science 340 (2005) 257 - 272.