Picture Languages Generated by Assembling Tiles

• Autorzy: Bonizzoni P. , Ferretti C. , Mary A. R. S. , Mauri G.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

picture languages; tiling rule systems; power of TRuS systems; Wang systems

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 110, nr 1-4
• Strony: 77--93
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Bonizzoni P.

autor

Ferretti C.

autor

Mary A. R. S.

autor

Mauri G.

• Dipartimento di Informatica Sistemistica e Comunicazione, Universita degli Studi di Milano- Bicocca, Viale Sarca 336, 20126 Milano, Italy,

Bibliografia

• [1] M. Anselmo, D. Giammarresi, M. Madonia, New operations and regular expressions for two-dimensional languages over one-letter alphabet, Theoretical Computer Science 340 (2005) 408 - 431.
• [2] M. Anselmo,M.Madonia Deterministic Two-Dimensional Languages over One-Letter Alphabet, Lect.Notes in Comp.Sci. 4728 (2007) 147-159.
• [3] A. Bertoni, M. Goldwurm, V. Lonati On the complexity of Unary Tiling-Recognizable Picture Lanaguages, Lect.Notes in Comp.Sci. 4393 (2007) 381-392.
• [4] A. Cherubini, S. Crespi Reghizzi and M. Pradella, Regional languages and Tiling: A Unifying Approach to Picture Grammars, Lect.Notes in Comp.Sci. 5162 (2008) 253-264.
• [5] A. Cherubini, S. Crespi Reghizzi, M. Pradella, P. San Pietro, Picture langugages : Tiling system versus Tile rewriting grammars, Theoretical Computer Science 356 (2006) 90 - 103.
• [6] S. Crespi Reghizzi, M. Pradella, Tile rewriting grammars and picture languages, Theoretical Computer Science 340 (2005) 257 - 272.
• [7] L. De Prophetis, S. Varricchio Recognizability of Rectangular Pictures by Wang Systems. Journal of Automata, Lang. and Combinatorics 2 (1997) 4, 269 - 288.
• [8] D. Giammarresi and A. Restivo, Two-dimensional languages, In "Handbook of Formal Languages" Vol.3, Eds. G. Rozenberg and A. Salomaa, Springer Verlag (1997) 215-267.
• [9] J. Kari, C. Moore, New Results on Alternating and Non-deterministic Two-Dimensional Finite-State Automata, Lect.Not. in Comp.Sci. 2010 (2001) 396-406.
• [10] D. Simplot, A characterization of Recognizable Picture Languages by tilings by finite sets, Theoretical Computer Science 218 (1999) 297 - 323.
• [11] E. Winfree, Algorithmic self-assembly of DNA: theoretical motivations and 2D assembly experiments. Journal of Biomol. Str. and Dynamics 11 (2000) 263-2