Affiliations: Dipartimento di Scienze dell'Informazione,
Università degli Studi di Milano Via Comelico 39/41, 20135 Milano – Italy.
{bertoni, goldwurm, lonati}@dsi.unimi.it
Note: [] Address for correspondence: Dip. Scienze
dell'Informazione, Università degli Studi di Milano, Via Comelico
39/41, 20135 Milano, Italy
Abstract: In this paper we consider the classes REC1 and UREC1 of unary
picture languages that are tiling recognizable and unambiguously tiling
recognizable, respectively. By representing unary pictures by quasi-unary
strings we characterize REC1 (resp. UREC1) as the class of quasi-unary
languages recognized by nondeterministic (resp. unambiguous) linearly
space-bounded one-tape Turing machines with constraint on the number of head
reversals. We apply such a characterization in two directions. First we prove
that the binary string languages encoding tiling recognizable unary square
languages lies between NTIME(2n) and NTIME(4n); by separation results, this
implies there exists a non-tiling recognizable unary square language whose
binary representation is a language in NTIME(4n log n). In the other direction,
by means of results on picture languages, we are able to compare the power of
deterministic, unambiguous and nondeterministic one-tape Turing machines that
are linearly space-bounded and have constraint on the number of head
reversals.
