Picture Languages Generated by Assembling Tiles

Issue title: Theory that Counts: To Oscar Ibarra on His 70th Birthday

Article type: Research Article

Authors: Bonizzoni, Paola | Ferretti, Claudio | Mary, A. Roslin Sagaya | Mauri, Giancarlo

Affiliations: Dipartimento di Informatica Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336, 20126 Milano, Italy. {anthonath, bonizzoni, ferretti, mauri}@disco.unimib.it

Note: [] Address for correspondence: Dipartimento di Informatica Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336, 20126 Milano, Italy

Abstract: We propose a new formalism for generating picture languages based on an assembly mechanism of tiles that uses rules having a context and a replacement site. More precisely, a picture language will be generated from a finite set of initial pictures by iteratively applying rewriting rules from a given finite set of rules, called a tiling rule system (TRuS system). We prove that the TRuS systems have a greater generative capacity than the tiling systems of Giammarresi and Restivo. This is due mainly to the use of the notion of replacement site, but we further characterize the difference between these systems by comparing them to Wang systems.

DOI: 10.3233/FI-2011-529

Journal: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 77-93, 2011