We 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 |