The Complexity of Unary Tiling Recognizable Picture Languages: Nondeterministic and Unambiguous Cases

• Autorzy: Bertoni A. , Goldwurm M. , Lonati V.
• Języki publikacji: EN

Abstrakty

EN

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(2^n) and NTIME(4^n); by separation results, this implies there exists a non-tiling recognizable unary square language whose binary representation is a language in NTIME(4^n 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.

Słowa kluczowe

EN

two-dimensional languages; tiling systems; linearly space-bounded Turing machine; head reversal-bounded computation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 91, nr 2
• Strony: 231--249
• Opis fizyczny: bibliogr. 17 poz., tab.

Twórcy

autor

Bertoni A.

autor

Goldwurm M.

autor

Lonati V.

• Dipartimento di Scienze dell'Informazione, Universita degli Studi di Milano Via Comelico 39/41, 20135 Milano -Italy,

Bibliografia

• [1] M. Agrawal, N. Kayal, N. Saxena. PRIMES is in P. Annals of Mathematics, 160(2): 781-793, 2004.
• [2] M. Anselmo, D. Giammarresi, M. Madonia. Regular expressions for two-dimensional languages over oneletter alphabet. In Proc. 8th DLT, C.S. Calude, E. Calude and M.J. Dinneen (Eds.), LNCS 3340, 63-75, Springer, 2004.
• [3] M. Anselmo, D. Giammarresi, M. Madonia, A. Restivo. Unambiguous recognizable two-dimensional languages. Theoretical Informatics and Applications 40(2): 277-293, 2006.
• [4] M. Anselmo, M. Madonia. Deterministic and unambiguous two-dimensional languages over one-letter alphabet. To appear in Theoretical Computer Science. Preliminary version in Proc. CAI 2007, S. Bozapalidis and G. Rahonis (Eds.), LNCS 4728, 147-159, Springer, 2007.
• [5] D. Giammarresi, A. Restivo. Recognizable picture languages. Int. J. Pattern Recognition and Artificial Intelligence 6: 31-42, 1992.
• [6] D. Giammarresi, A. Restivo. Two-dimensional languages. In Handbook of Formal Languages, G. Rosenberg and A. Salomaa (Eds.), Vol. III, 215 - 268, Springer-Verlag, 1997.
• [7] D. Giammarresi, A. Restivo, S. Seibert,W. Thomas.Monadic second order logic over rectangular pictures and recognizability by tiling system. Information and Computation, 125(1):32-45, 1996.
• [8] K. Inoue, I. Takanami. A survey of two-dimensional automata theory. In Proc. 5th Int. Meeting of Young Computer Scientists, J. Dasson, J. Kelemen (Eds.), LNCS 381, 72-91, Springer-Verlag, 1990.
• [9] J. Kari, C. Moore. New results on alternating and non-deterministic two-dimensional finite state automata. In Proc. 18th STACS, A. Ferreira, H. Reichel (Eds.), LNCS 2010, 396-406, Springer-Verlag, 2001.
• [10] O. Matz. Regular expressions and context-free grammars for picture languages. In Proc. 14th STACS, LNCS 1200, 283-294, Springer-Verlag, 1997.
• [11] O. Matz. Dot-depth and monadic quantifier alternation over pictures. Ph.D. thesis, Technical Report 99-08, RWTH AAchen, 1999.
• [12] O. Matz. Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures. Theoretical Computer Science, 270(1-2): 1-70, Elsevier 2002.
• [13] A.R. Meyer and L.J. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In Proc. 13th Annual IEEE Symp. on Switching and Automata Theory, 125-129, 1972.
• [14] A.R. Meyer and L.J. Stockmeyer. Words problems requiring exponential time. In Proc. 5th ACM Symp. On Theory of Computing, 1-9, 1973.
• [15] J. I. Seiferas, M. J. Fischer, A. R. Meyer. Separating nondeterministic time complexity classes. Journal of ACM, 25(1): 146-167, 1978.
• [16] R. Siromoney.Advances in array languages. In Graph-grammars and their applications to Computer Science, Ehrig et al. Eds., LNCS 291, 549-563, Springer-Verlag, 1987.
• [17] K. Wagner, G. Wechsung. Computational complexity. D. Reidel Publishing Company, 1986.