Consiglio Nazionale delle Ricerche

Tipo di prodottoArticolo in rivista
TitoloA SAT-Based Parser and Completer for Pictures Specified by Tiling
Anno di pubblicazione2008
Autore/iM. Pradella, S. Crespi Reghizzi
Affiliazioni autoriPolitecnico di Milano
Autori CNR e affiliazioni
  • inglese
AbstractPictures or patterns have been formally specified by different methods such as grammars. An alternative approach is based on tiling systems (TS) (Wang tiles are an analogous and equivalent formalism), whereby the picture is obtained by first covering it with a specified set of 2 × 2 tiles, then by performing a pixel by pixel mapping. TS are a powerful technique: the corresponding pictures can be recognized by non-deterministic cellular automata, which are more powerful than the four-ways automata. The difficulty to write such specifications for non- elementary pictures, and the NP-complete computational complexity of TS picture recognition have so far blocked any attempt to application. We have implemented a recognizer and generator for TS pictures in a very attractive, unconventional way, by transforming the tiling problem into a SAT (Boolean satisfiability) one, then using an efficient off-the-shelf SAT-solver. The prototype is fast enough to experiment on reasonably sized samples, and has the bonus of being able to complete or extrapolate a partial or noisy picture. The tool is invaluable to assist in writing picture specification. A series of examples shows how to specify patterns using TS.
Lingua abstractinglese
Altro abstract-
Lingua altro abstract-
Pagine da555
Pagine a566
Pagine totali-
RivistaPattern recognition
Attiva dal 1968
Editore: Pergamon Press. - New York
Paese di pubblicazione: Regno Unito
Lingua: inglese
ISSN: 0031-3203
Titolo chiave: Pattern recognition
Titolo proprio: Pattern recognition.
Titolo abbreviato: Pattern recogn.
Numero volume della rivista41
Fascicolo della rivista-
Verificato da refereeSì: Internazionale
Stato della pubblicazione-
Indicizzazione (in banche dati controllate)
  • ISI Web of Science (WOS) (Codice:000250695500010)
Parole chiaveSyntactic pattern recognition, Picture languages, Tiling systems, Wang tiles, Two-dimensional grammars and languages
Link (URL, URI)-
Titolo parallelo-
Data di accettazione-
Note/Altre informazioni-
Strutture CNR
  • IEIIT — Istituto di elettronica e di ingegneria dell'informazione e delle telecomunicazioni
Moduli/Attività/Sottoprogetti CNR
  • ICT.P09.008.001 : Metodi e Strumenti per la Progettazione di Sistemi Software-Intensive ad Elevata Complessità
Progetti Europei-
a SAT-based parser (documento privato )
Tipo documento: application/pdf

Dati associati a vecchie tipologie
I dati associati a vecchie tipologie non sono modificabili, derivano dal cambiamento della tipologia di prodotto e hanno solo valore storico.
  • Academic Press Elsevier, Amsterdam (Paesi Bassi)

Dati storici
I dati storici non sono modificabili, sono stati ereditati da altri sistemi (es. Gestione Istituti, PUMA, ...) e hanno solo valore storico.
Area disciplinareComputer Science & Engineering
Area valutazione CIVRIngegneria industriale e informatica