Tile Rewriting Grammars

  • Stefano Crespi Reghizzi
  • Matteo Pradella
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


Past proposals for applying to pictures or 2D languages the generative grammar approach do not match in our opinion the elegance and descriptive adequacy that made Context Free grammars so successful for 1D languages. In a renewed attempt, a model named Tile Rewriting Grammar is introduced combining the rewriting rules with the Tiling System of Giammaresi and Restivo which define the family of Recognizable 2D languages. The new grammars have isometric rewriting rules which for string languages are equivalent to CF rules. TRG have the capacity to generate a sort of 2D analogues of Dyck languages. Closure properties of TRG are proved for some basic operations. TRG strictly include TS as well as the context-free picture grammars of Matz.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Henning Fernau and Rudolf Freund. Bounded parallelism in array grammars used for character recognition. In Petra Perner, Patrick Wang, and Azriel Rosenfeld, editors, Advances in Structural and Syntactical Pattern Recognition (Proceedings of the SSPR’96), volume 1121, pages 40–49. Springer-Verlag, 1996.Google Scholar
  2. 2.
    Dora Giammarresi and Antonio Restivo. Recognizable picture languages. International Journal Pattern Recognition and Artificial Intelligence, 6(2–3):241–256, 1992. Special Issue on Parallel Image Processing.CrossRefGoogle Scholar
  3. 3.
    Dora Giammarresi and Antonio Restivo. Two-dimensional languages. In Arto Salomaa and Grzegorz Rozenberg, editors, Handbook of Formal Languages, volume 3, Beyond Words, pages 215–267. Springer-Verlag, Berlin, 1997.Google Scholar
  4. 4.
    Katsushi Inoue and Akira Nakamura. Some properties of two-dimensional on-line tessellation acceptors. Information Sciences, 13:95–121, 1977.CrossRefMathSciNetGoogle Scholar
  5. 5.
    Oliver Matz. Regular expressions and context-free grammars for picture languages. In 14th Annual Symposium on Theoretical Aspects of Computer Science, volume 1200 of Lecture Notes in Computer Science, pages 283–294, Lübeck, Germany, 27 February–March 1 1997. Springer-Verlag.Google Scholar
  6. 6.
    Rani Siromoney. Advances in Array Languages. In Hartmut Ehrig, Manfred Nagl, Grzegorz Rozenberg, and Azriel Rosenfeld, editors, Proc. 3rd Int. Workshop on Graph-Grammars and Their Application to Computer Science, volume 291 of Lecture Notes in Computer Science, pages 549–563. Springer-Verlag, 1987.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Stefano Crespi Reghizzi
    • 1
  • Matteo Pradella
    • 1
  1. 1.DEI — Politecnico di Milano and CNR IEIIT-MIMilanoItaly

Personalised recommendations