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.
Picture language, Picture grammar, 2D language, Tiling system, Recognizable picture language, Tile rewriting grammar, 2D regular; language; Autoinclusive derivation
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/553820
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 19
  • ???jsp.display-item.citation.isi??? 12
social impact