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 [10.1007/978-3-540-70918-3_33].

On the complexity of unary tiling-recognizable picture languages

A. Bertoni
Primo
;
M. Goldwurm
Secondo
;
V. Lonati
Ultimo
2007

Abstract

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).
unary picture languages; tiling systems; Turing machine head reversal
Settore INF/01 - Informatica
2007
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
stacs07_def.pdf

accesso riservato

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 357.18 kB
Formato Adobe PDF
357.18 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Bertoni2007_Chapter_OnTheComplexityOfUnaryTiling-R.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 498.61 kB
Formato Adobe PDF
498.61 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/28988
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 7
social impact