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, even in the case of one-letter alphabet picture languages. This is due mainly to the use of the notion of replacement. © Springer-Verlag Berlin Heidelberg 2009.

Bonizzoni, P., Ferretti, C., Anthonath Roslin Sagaya, M., Mauri, G. (2009). Picture languages generated by assembling tiles. In Language and Automata Theory and Applications (pp.224-235). Berlin : Springer-Verlag [10.1007/978-3-642-00982-2_19].

Picture languages generated by assembling tiles

BONIZZONI, PAOLA;FERRETTI, CLAUDIO;MAURI, GIANCARLO
2009

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, even in the case of one-letter alphabet picture languages. This is due mainly to the use of the notion of replacement. © Springer-Verlag Berlin Heidelberg 2009.
slide + paper
picture languages; tiling systems; formal languages
English
LATA 2009
2009
A.H. Dediu, A.M. Ionescu, C. Martın-Vide
Language and Automata Theory and Applications
978-3-642-00981-5
2009
5457
224
235
none
Bonizzoni, P., Ferretti, C., Anthonath Roslin Sagaya, M., Mauri, G. (2009). Picture languages generated by assembling tiles. In Language and Automata Theory and Applications (pp.224-235). Berlin : Springer-Verlag [10.1007/978-3-642-00982-2_19].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/10281/11996
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 1
Social impact