Tile Rewriting Grammars (TRG) are a new model for defining picture languages. A rewriting rule changes a homogeneous rectangular subpicture into a isometric one tiled with specified tiles. Derivation and language generation with TRG rules are similar to contextfree grammars. A normal form and some closure properties are presented. We prove this model has greater generative capacity than the Tiling Systems of Giammarresi and Restivo and the grammars of Matz, another generalization of context free string grammars to 2D. Examples are shown for pictures made by nested frames and spirals.
Tile rewriting grammars and picture languages
CRESPI REGHIZZI, STEFANO;PRADELLA, MATTEO
2005-01-01
Abstract
Tile Rewriting Grammars (TRG) are a new model for defining picture languages. A rewriting rule changes a homogeneous rectangular subpicture into a isometric one tiled with specified tiles. Derivation and language generation with TRG rules are similar to contextfree grammars. A normal form and some closure properties are presented. We prove this model has greater generative capacity than the Tiling Systems of Giammarresi and Restivo and the grammars of Matz, another generalization of context free string grammars to 2D. Examples are shown for pictures made by nested frames and spirals.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
tilerewriting.pdf
Accesso riservato
:
Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione
550.39 kB
Formato
Adobe PDF
|
550.39 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.