IRIS Institutional Research Information System - AIR Archivio Istituzionale della Ricerca
IRIS è il sistema di gestione integrata dei dati della ricerca (persone, progetti, pubblicazioni, attività) adottato dall'Università degli Studi di Milano.
AIR nasce in UNIMI nel 2006 con lo scopo di raccogliere, documentare e conservare le informazioni sulla produzione scientifica dell'Università degli Studi di Milano e costituisce di fatto l'Anagrafe della ricerca dell'Ateneo.
EnglishWe give a characterization, in terms of computational complexity, of the family Rec 1 of the unary picture languages that are tiling recognizable. We introduce quasi-unary strings to represent unary pictures and we prove that any unary picture language L is in Rec 1 if and only if the set of all quasi-unary strings encoding the elements of L is recognizable by a one-tape nondeterministic Turing machine that is space and head-reversal linearly bounded. In particular, the result implies that the family of binary string languages corresponding to tiling-recognizable square languages lies between NTime(2 n ) and NTime(4 n ). This also implies the existence of a nontiling-recognizable unary square language that corresponds to a binary string language recognizable in nondeterministic time O(4 n logn).
On the complexity of unary tiling-recognizable picture languages / A. Bertoni, M. Goldwurm, V. Lonati (LECTURE NOTES IN COMPUTER SCIENCE). - In: STACS 2007 / [a cura di] W. Thomas, P. Weil. - Prima edizione. - Berlin : Springer, 2007. - ISBN 9783540709176. - pp. 381-392 (( Intervento presentato al 24. convegno Annual Symposium on Theoretical Aspects of Computer Science tenutosi a Aachen nel 2007.
| Titolo: | On the complexity of unary tiling-recognizable picture languages |
| Autori: | BERTONI, ALBERTO (Primo) GOLDWURM, MASSIMILIANO (Secondo) LONATI, VIOLETTA (Ultimo) |
| Parole Chiave: | unary picture languages; tiling systems; Turing machine head reversal |
| Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
| Data di pubblicazione: | 2007 |
| Digital Object Identifier (DOI): | http://dx.doi.org/10.1007/978-3-540-70918-3_33 |
| Tipologia: | Book Part (author) |
| Appare nelle tipologie: | 03 - Contributo in volume |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| stacs07_def.pdf | Post-print, accepted manuscript ecc. (versione accettata dall'editore) | Administrator Richiedi una copia | ||
| Bertoni2007_Chapter_OnTheComplexityOfUnaryTiling-R.pdf | Publisher's version/PDF | Administrator Richiedi una copia |
Copyright © 2021