Two formal models of pictures, i.e., two dimensional (2D) languages are compared: tiling systems and tile rewriting grammars, which resp. extend to 2D the regular and context-free languages. Two results extending classical language properties into 2D are proved. First, non-recursive tile writing grammars (TRG) coincide with tiling systems (TS). Second, non-self-embedding TRG are suitably defined as corner grammars, showing that they generate TS languages. The proofs exploit newly introduced language substitutions, also nested and iterated.
Picture languages: Tiling systems versus tile rewriting grammars
CHERUBINI, ALESSANDRA;CRESPI REGHIZZI, STEFANO;PRADELLA, MATTEO;SAN PIETRO, PIERLUIGI
2006-01-01
Abstract
Two formal models of pictures, i.e., two dimensional (2D) languages are compared: tiling systems and tile rewriting grammars, which resp. extend to 2D the regular and context-free languages. Two results extending classical language properties into 2D are proved. First, non-recursive tile writing grammars (TRG) coincide with tiling systems (TS). Second, non-self-embedding TRG are suitably defined as corner grammars, showing that they generate TS languages. The proofs exploit newly introduced language substitutions, also nested and iterated.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
Pict_lang06.pdf
Accesso riservato
:
Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione
263.64 kB
Formato
Adobe PDF
|
263.64 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.