Consiglio Nazionale delle Ricerche

Tipo di prodottoArticolo in rivista
TitoloTiling Systems versus Tile Rewriting Grammars
Anno di pubblicazione2006
FormatoCartaceo
Autore/iA. Cherubini, S. Crespi Reghizzi, M. Pradella, P. San Pietro
Affiliazioni autoriPolitecnico di Milano
Autori CNR e affiliazioni
  • STEFANO CRESPI REGHIZZI VQR
  • MATTEO PRADELLA
Lingua/e
  • inglese
AbstractTwo formal models of pictures, i.e., two dimensional (2D) languages are compared: tiling systems and tile rewriting grammars, which resp. extend to 2D the regular and context-free languages. Two results extending classical language properties into 2D are proved. First, non-recursive tile writing grammars (TRG) coincide with tiling systems (TS). Second, non-self-embedding TRG are suitably defined as corner grammars, showing that they generate TS languages. The proofs exploit newly introduced language substitutions, also nested and iterated.
Lingua abstractinglese
Altro abstract-
Lingua altro abstract-
Pagine da90
Pagine a103
Pagine totali-
RivistaTheoretical computer science
Attiva dal 1975
Editore: Elsevier - Lausanne ;
Paese di pubblicazione: Paesi Bassi
Lingua: inglese
ISSN: 0304-3975
Titolo chiave: Theoretical computer science
Titolo abbreviato: Theor. comp. sci.
Numero volume della rivista356
Fascicolo della rivista-
DOI10.1016/j.tcs.2006.01.038
Verificato da refereeSì: Internazionale
Stato della pubblicazione-
Indicizzazione (in banche dati controllate)
  • ISI Web of Science (WOS) (Codice:000237197900008)
Parole chiavePicture language, Picture grammar, 2D language, Tiling system, Recognizable picture language
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 CNR
    Progetti Europei-
    Allegati
    • Picture languages Tiling

    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.
    Editore
    • 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.
    Rivista ISITHEORETICAL COMPUTER SCIENCE [03116J0]