Consiglio Nazionale delle Ricerche

Tipo di prodottoArticolo in rivista
TitoloA unifying approach to picture grammars
Anno di pubblicazione2011
Autore/iPradella M.; Cherubini A.; Crespi Reghizzi S.
Affiliazioni autoriDipartimento di Elettronica e Informazione, Politecnico di Milano, P.zza L. da Vinci, 32, 20133 Milano, Italy; Dipartimento di Matematica, Politecnico di Milano, P.zza L. da Vinci, 32, 20133 Milano, Italy
Autori CNR e affiliazioni
  • inglese
AbstractSeveral old and recent classes of picture grammars, that variously extend context-free string grammars in two dimensions, are based on rules that rewrite arrays of pixels. Such grammars can be unified and extended using an approach, whereby the right part of a rule is formalized by means of a finite set of permitted tiles. We focus on a simple type of tiling, named regional, and define the corresponding regional tile grammars. They include both Siromoneys (or Matzs) Kolam grammars and their generalization by Pr??a, as well as Drewess grid grammars. Regionally defined pictures can be recognized with polynomial-time complexity by an algorithm extending the CKY one for strings. Regional tile grammars and languages are strictly included into our previous tile grammars and languages, and are incomparable with Giammarresi-Restivo tiling systems (or Wang systems). © 2011 Elsevier Inc.
Lingua abstractinglese
Altro abstract-
Lingua altro abstract-
Pagine da1246
Pagine a1267
Pagine totali-
RivistaInformation and computation (Print)
Attiva dal 1987
Editore: Academic Press, - San Diego
Paese di pubblicazione: Stati Uniti d'America
Lingua: inglese
ISSN: 0890-5401
Titolo chiave: Information and computation (Print)
Titolo proprio: Information and computation. (Print)
Titolo abbreviato: Inf. comput. (Print)
Numero volume della rivista209
Fascicolo della rivista9
Verificato da refereeSì: Internazionale
Stato della pubblicazionePublished version
Indicizzazione (in banche dati controllate)
  • Scopus (Codice:2-s2.0-79960894376)
Parole chiave2D language, CKY algorithm, Picture grammar, Picture language, Syntactic pattern recognition, Tiling
Link (URL, URI)
Titolo parallelo-
Data di accettazione-
Note/Altre informazioni-
Strutture CNR
  • IEIIT — IEIIT - Sede secondaria di Milano
Moduli CNR-
Progetti Europei-
  • A unifying approach to picture grammars