{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:05Z","timestamp":1759638965383,"version":"3.40.3"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319155784"},{"type":"electronic","value":"9783319155791"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-15579-1_55","type":"book-chapter","created":{"date-parts":[[2015,2,23]],"date-time":"2015-02-23T08:36:13Z","timestamp":1424680573000},"page":"703-715","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Nivat Theorem for Weighted Picture Automata and Weighted MSO Logic"],"prefix":"10.1007","author":[{"given":"Parvaneh","family":"Babari","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manfred","family":"Droste","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"issue":"2","key":"55_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1051\/ita:2006008","volume":"40","author":"M Anselmo","year":"2006","unstructured":"Anselmo, M., Giammarresi, D., Madonia, M., Restivo, A.: Unambiguous recognizable two-dimensional languages. Theoretical Information and Application 40(2), 277\u2013293 (2006)","journal-title":"Theoretical Information and Application"},{"key":"55_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/978-3-642-02737-6_2","volume-title":"Developments in Language Theory","author":"B Bollig","year":"2009","unstructured":"Bollig, B., Gastin, P.: Weighted versus probabilistic logics. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol. 5583, pp. 18\u201338. Springer, Heidelberg (2009)"},{"key":"55_CR3","first-page":"159","volume":"10","author":"S Bozapalidis","year":"2005","unstructured":"Bozapalidis, S., Grammatikopoulou, A.: Recognizable picture series. Journal of Automata, Languages and Combinatorics 10, 159\u2013183 (2005)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"55_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/978-3-540-87531-4_28","volume-title":"Computer Science Logic","author":"K Chatterjee","year":"2008","unstructured":"Chatterjee, K., Doyen, L., Henzinger, T.A.: Quantitative languages. In: Kaminski, M., Martini, S. (eds.) CSL 2008. LNCS, vol. 5213, pp. 385\u2013400. Springer, Heidelberg (2008)"},{"key":"55_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-642-03409-1_2","volume-title":"Fundamentals of Computation Theory","author":"K Chatterjee","year":"2009","unstructured":"Chatterjee, K., Doyen, L., Henzinger, T.A.: Alternating weighted automata. In: Kuty\u0142owski, M., Charatonik, W., \u0118bala, M. (eds.) FCT 2009. LNCS, vol. 5699, pp. 3\u201313. Springer, Heidelberg (2009)"},{"issue":"3\u201310","key":"55_CR6","first-page":"1","volume":"6","author":"K Chatterjee","year":"2010","unstructured":"Chatterjee, K., Doyen, L., Henzinger, T.A.: Expressiveness and closure properties for quantitative languages. Logical Methods in Computer Science 6(3\u201310), 1\u201323 (2010)","journal-title":"Logical Methods in Computer Science"},{"key":"55_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-642-04081-8_17","volume-title":"CONCUR 2009 - Concurrency Theory","author":"K Chatterjee","year":"2009","unstructured":"Chatterjee, K., Doyen, L., Henzinger, T.A.: Probabilistic weighted automata. In: Bravetti, M., Zavattaro, G. (eds.) CONCUR 2009. LNCS, vol. 5710, pp. 244\u2013258. Springer, Heidelberg (2009)"},{"issue":"1\u20132","key":"55_CR8","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.tcs.2007.02.055","volume":"380","author":"M Droste","year":"2007","unstructured":"Droste, M., Gastin, P.: Weighted automata and weighted logics. Theoretical Computer Science 380(1\u20132), 69\u201386 (2007)","journal-title":"Theoretical Computer Science"},{"key":"55_CR9","unstructured":"Droste, M., Kuske, D.: Weighted automata. In: Pin, J.-E. (ed.) Handbook: \u201cAutomata: from Mathematics to Applications\u201d. European Mathematical Society (to appear)"},{"key":"55_CR10","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.ic.2012.10.001","volume":"220\u2013221","author":"M Droste","year":"2012","unstructured":"Droste, M., Meinecke, I.: Weighted automata and weighted MSO logics for average- and longtime-behaviors. Information and Computation 220\u2013221, 44\u201359 (2012)","journal-title":"Information and Computation"},{"key":"55_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/978-3-662-43951-7_15","volume-title":"Automata, Languages, and Programming","author":"M Droste","year":"2014","unstructured":"Droste, M., Perevoshchikov, V.: A Nivat theorem for weighted timed automata and weighted relative distance logic. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 171\u2013182. Springer, Heidelberg (2014)"},{"key":"55_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/11779148_6","volume-title":"Developments in Language Theory","author":"M Droste","year":"2006","unstructured":"Droste, M., Rahonis, G.: Weighted automata and weighted logics on infinite words. In: Ibarra, O.H., Dang, Z. (eds.) DLT 2006. LNCS, vol. 4036, pp. 49\u201358. Springer, Heidelberg (2006)"},{"key":"55_CR13","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.tcs.2011.11.008","volume":"418","author":"M Droste","year":"2012","unstructured":"Droste, M., Vogler, H.: Weighted automata and multi-valued logics over arbitrary bounded lattices. Theoretical Computer Science 418, 14\u201336 (2012)","journal-title":"Theoretical Computer Science"},{"key":"55_CR14","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1016\/j.tcs.2006.08.025","volume":"366","author":"M Droste","year":"2006","unstructured":"Droste, M., Vogler, H.: Weighted tree automata and weighted logics. Theoretical Computer Science 366, 228\u2013247 (2006)","journal-title":"Theoretical Computer Science"},{"key":"55_CR15","unstructured":"Eilenberg, S.: Automata, Languages, and Machines, vol. A. Academic Press (1974)"},{"issue":"1","key":"55_CR16","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/s00224-009-9225-3","volume":"48","author":"I Fichtner","year":"2011","unstructured":"Fichtner, I.: Weighted picture automata and weighted logics. Theory of Computing Systems 48(1), 48\u201378 (2011)","journal-title":"Theory of Computing Systems"},{"key":"55_CR17","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/j.tcs.2007.01.019","volume":"374","author":"I Fichtner","year":"2007","unstructured":"Fichtner, I.: Characterizations of recognizable picture series. Theoretical Computer Science 374, 214\u2013228 (2007)","journal-title":"Theoretical Computer Science"},{"key":"55_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/11672142_25","volume-title":"STACS 2006","author":"I M\u00e4urer","year":"2006","unstructured":"M\u00e4urer, I.: Weighted picture automata and weighted logics. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 313\u2013324. Springer, Heidelberg (2006)"},{"key":"55_CR19","volume-title":"Syntactic Methods in Pattern Recognition","author":"KS Fu","year":"1974","unstructured":"Fu, K.S.: Syntactic Methods in Pattern Recognition. Academic Press, New York (1974)"},{"issue":"2, 3","key":"55_CR20","first-page":"256","volume":"6","author":"D Giammarresi","year":"1992","unstructured":"Giammarresi, D., Restivo, A.: Recognizable picture languages. International Journal of Pattern Recognition and Artificial Intelligence 6(2, 3), 256 (1992)","journal-title":"International Journal of Pattern Recognition and Artificial Intelligence"},{"issue":"3","key":"55_CR21","doi-asserted-by":"crossref","first-page":"399","DOI":"10.3233\/FI-1996-253411","volume":"25","author":"D Giammarresi","year":"1996","unstructured":"Giammarresi, D., Restivo, A.: Two-dimensional finite state recognizability. Fundamental Informaticae 25(3), 399\u2013422 (1996)","journal-title":"Fundamental Informaticae"},{"key":"55_CR22","doi-asserted-by":"crossref","unstructured":"Giammarresi, D., Restivo, A.: Two-dimensional languages. In: Rozenberg, G., Salomaa, A., (eds.) Handbook of Formal Languages, vol. 3, pp. 215\u2013267. Springer (1997)","DOI":"10.1007\/978-3-642-59126-6_4"},{"issue":"1","key":"55_CR23","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1006\/inco.1996.0018","volume":"125","author":"D Giammarresi","year":"1996","unstructured":"Giammarresi, D., Restivo, A., Seibert, S., Thomas, W.: Monadic second-order logic over rectangular pictures and recognizability by tiling systems. Information and Computation 125(1), 32\u201345 (1996)","journal-title":"Information and Computation"},{"key":"55_CR24","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0255(77)90023-8","volume":"13","author":"K Inoue","year":"1977","unstructured":"Inoue, K., Nakamura, A.: Some properties of two-dimensional on-line tessellation acceptors. Information Sciences 13, 95\u2013121 (1977)","journal-title":"Information Sciences"},{"key":"55_CR25","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0020-0255(91)90008-I","volume":"55","author":"K Inoue","year":"1991","unstructured":"Inoue, K., Takanami, I.: A survey of two-dimentional automata theory. Information Sciences 55, 99\u2013121 (1991)","journal-title":"Information Sciences"},{"key":"55_CR26","doi-asserted-by":"crossref","unstructured":"Kuich, W., Salomaa, A.: Semirings, Automata, Languages, vol. 6. EATCS Monographs, Theoretical Computer Science. Springer (1986)","DOI":"10.1007\/978-3-642-69959-7"},{"key":"55_CR27","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/S0304-3975(96)00283-6","volume":"178","author":"M Latteux","year":"1997","unstructured":"Latteux, M., Simplot, D.: Recognizable picture languages and domino tiling. Theoretical Computer Science 178, 275\u2013283 (1997)","journal-title":"Theoretical Computer Science"},{"issue":"5\u20136","key":"55_CR28","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1023\/A:1023027932419","volume":"91","author":"K Lindgren","year":"1998","unstructured":"Lindgren, K., Moore, C., Nordahl, M.: Complexity of two-dimensional patterns. Journal of Statistical Physics 91(5\u20136), 909\u2013951 (1998)","journal-title":"Journal of Statistical Physics"},{"key":"55_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/BFb0053551","volume-title":"Foundations of Software Science and Computation Structures","author":"O Matz","year":"1998","unstructured":"Matz, O.: On piecewise testable, starfree, and recognizable picture languages. In: Nivat, M. (ed.) FOSSACS 1998. LNCS, vol. 1378, pp. 203\u2013210. Springer, Heidelberg (1998)"},{"key":"55_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/11753728_25","volume-title":"Computer Science \u2013 Theory and Applications","author":"I Meinecke","year":"2006","unstructured":"Meinecke, I.: Weighted logics for traces. In: Grigoriev, D., Harrison, J., Hirsch, E.A. (eds.) CSR 2006. LNCS, vol. 3967, pp. 235\u2013246. Springer, Heidelberg (2006)"},{"key":"55_CR31","unstructured":"Minski, M., Papert, S.: Perceptron. M.I.T Press, Cambridge (1969)"},{"key":"55_CR32","doi-asserted-by":"crossref","unstructured":"Salomaa, A., Soittola, M.: Automata-Theoretic Aspects of Formal Power Series. Texts and Monographs on Computer Science. Springer (1978)","DOI":"10.1007\/978-1-4612-6264-0"},{"issue":"2","key":"55_CR33","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/S0304-3975(98)00328-4","volume":"218","author":"D Simplot","year":"1999","unstructured":"Simplot, D.: A characterization of recognizable picture languages by tilings by finite sets. Theoretical Computer Science 218(2), 297\u2013323 (1999)","journal-title":"Theoretical Computer Science"},{"key":"55_CR34","doi-asserted-by":"crossref","unstructured":"Smith, R.A.: Two-dimensional formal languages and pattern recognition by cellular automata. In: 12th IEEE FOCS Conference Record, pp. 144\u2013152 (1971)","DOI":"10.1109\/SWAT.1971.29"},{"key":"55_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/3-540-54233-7_154","volume-title":"Automata, Languages and Programming","author":"W Thomas","year":"1991","unstructured":"Thomas, W.: On logics, tilings, and automata. In: Leach Albert, J., Monien, B., Rodr\u00edguez-Artalejo, M. (eds.) ICALP 1991. LNCS, vol. 510, pp. 441\u2013454. Springer, Heidelberg (1991)"},{"key":"55_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/3-540-63165-8_191","volume-title":"Automata, Languages and Programming","author":"T Wilke","year":"1997","unstructured":"Wilke, T.: Star-free picture expressions are strictly weaker than first-order logic. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol. 1256, pp. 347\u2013357. Springer, Heidelberg (1997)"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-15579-1_55","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T05:07:43Z","timestamp":1674191263000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-15579-1_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319155784","9783319155791"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-15579-1_55","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"24 February 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}