{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:49:51Z","timestamp":1725511791711},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540709176"},{"type":"electronic","value":"9783540709183"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70918-3_33","type":"book-chapter","created":{"date-parts":[[2007,5,23]],"date-time":"2007-05-23T19:41:23Z","timestamp":1179949283000},"page":"381-392","source":"Crossref","is-referenced-by-count":4,"title":["On the Complexity of Unary Tiling-Recognizable Picture Languages"],"prefix":"10.1007","author":[{"given":"Alberto","family":"Bertoni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Massimiliano","family":"Goldwurm","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Violetta","family":"Lonati","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"33_CR1","doi-asserted-by":"publisher","first-page":"781","DOI":"10.4007\/annals.2004.160.781","volume":"160","author":"M. Agrawal","year":"2004","unstructured":"Agrawal, M., Kayal, N., Saxena, N.: PRIMES is in P. Annals of Mathematics\u00a0160(2), 781\u2013793 (2004)","journal-title":"Annals of Mathematics"},{"key":"33_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/978-3-540-30550-7_6","volume-title":"Developments in Language Theory","author":"M. Anselmo","year":"2004","unstructured":"Anselmo, M., Giammarresi, D., Madonia, M.: Regular expressions for two-dimensional languages over one-letter alphabet. In: Calude, C.S., Calude, E., Dinneen, M.J. (eds.) DLT 2004. LNCS, vol.\u00a03340, pp. 63\u201375. Springer, Heidelberg (2004)"},{"key":"33_CR3","doi-asserted-by":"crossref","unstructured":"Giammarresi, D., Restivo, A.: Recognizable picture languages. Int. J. Pattern Recognition and Artificial Intelligence, Special Issue on Parallel Image Processing, 31\u201342 (1992)","DOI":"10.1142\/9789812797872_0003"},{"key":"33_CR4","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/978-3-642-59126-6_4","volume-title":"Handbook of Formal Languages, vol. III","author":"D. Giammarresi","year":"1997","unstructured":"Giammarresi, D., Restivo, A.: Two-dimensional languages. In: Rosenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. III, pp. 215\u2013268. Springer, Heidelberg (1997)"},{"issue":"1","key":"33_CR5","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1006\/inco.1996.0018","volume":"125","author":"D. Giammarresi","year":"1996","unstructured":"Giammarresi, D., et al.: Monadic second order logic over rectangular pictures and recognizability by tiling system. Information and Computation\u00a0125(1), 32\u201345 (1996)","journal-title":"Information and Computation"},{"key":"33_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/BFb0015929","volume-title":"Machines, Languages, and Complexity","author":"K. Inoue","year":"1989","unstructured":"Inoue, K., Takanami, I.: A survey of two-dimensional automata theory. In: Dassow, J., Kelemen, J. (eds.) IMYCS 1988. LNCS, vol.\u00a0381, pp. 72\u201391. Springer, Heidelberg (1989)"},{"key":"33_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/3-540-44693-1_35","volume-title":"STACS 2001","author":"J. Kari","year":"2001","unstructured":"Kari, J., Moore, C.: New results on alternating and non-deterministic two-dimensional finite state automata. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 396\u2013406. Springer, Heidelberg (2001)"},{"key":"33_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/BFb0023466","volume-title":"STACS 97","author":"O. Matz","year":"1997","unstructured":"Matz, O.: Regular expressions and context-free grammars for picture languages. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol.\u00a01200, pp. 283\u2013294. Springer, Heidelberg (1997)"},{"key":"33_CR9","first-page":"125","volume-title":"Proc. 13th Annual IEEE Symp. on Switching and Automata Theory","author":"A.R. Meyer","year":"1972","unstructured":"Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential space. In: Proc. 13th Annual IEEE Symp. on Switching and Automata Theory, pp. 125\u2013129. IEEE Computer Society Press, Los Alamitos (1972)"},{"key":"33_CR10","first-page":"1","volume-title":"Proc. 5th ACM Symp. on Theory of Computing","author":"A.R. Meyer","year":"1973","unstructured":"Meyer, A.R., Stockmeyer, L.J.: Words problems requiring exponential time. In: Proc. 5th ACM Symp. on Theory of Computing, pp. 1\u20139. ACM Press, New York (1973)"},{"issue":"1","key":"33_CR11","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1145\/322047.322061","volume":"25","author":"J.I. Seiferas","year":"1978","unstructured":"Seiferas, J.I., Fischer, M.J., Meyer, A.R.: Separating nondeterministic time complexity classes. Journal of ACM\u00a025(1), 146\u2013167 (1978)","journal-title":"Journal of ACM"},{"key":"33_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1007\/3-540-18771-5_75","volume-title":"Graph-Grammars and Their Application to Computer Science","author":"R. Siromoney","year":"1987","unstructured":"Siromoney, R.: Advances in array languages. In: Ehrig, H., et al. (eds.) Graph Grammars 1986. LNCS, vol.\u00a0291, pp. 549\u2013563. Springer, Heidelberg (1987)"}],"container-title":["Lecture Notes in Computer Science","STACS 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70918-3_33.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T00:11:52Z","timestamp":1605744712000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70918-3_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540709176","9783540709183"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70918-3_33","relation":{},"subject":[]}}