Two-dimensional Languages and Picture Grammars

We have studied existing models of grammars for specifying 2D patterns and introduced more refined models based on tiling and on rewriting rules. We have characterized the capacity to generate different types of patterns, and the time complexity for pattern recognition.

Bibliography

  1. M. Pradella and S. Crespi Reghizzi: A SAT-based parser and completer for pictures specified by tiling, Pattern Recognition, Volume 41, Issue 2, February 2008, Pages 555-566
  2. S. Crespi Reghizzi and M. Pradella:A CKY parser for picture grammars, Information Processing Letters, Volume 105, 213-217, March 2008.
  3. A. Cherubini, S. Crespi-Reghizzi and M. Pradella; Regional languages and tiling: a unifying approach to picture grammars, MFCS 2008, Torun, August 2008.