{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T10:00:02Z","timestamp":1773655202059,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540857792","type":"print"},{"value":"9783540857808","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-85780-8_20","type":"book-chapter","created":{"date-parts":[[2008,9,9]],"date-time":"2008-09-09T05:23:54Z","timestamp":1220937834000},"page":"252-263","source":"Crossref","is-referenced-by-count":8,"title":["On the Decidability of the Equivalence for k-Valued Transducers"],"prefix":"10.1007","author":[{"given":"Rodrigo","family":"de Souza","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"20_CR1","unstructured":"Sakarovitch, J., Souza, R.: On the decomposition of k-valued rational relations. In: Albers, S., Weil, P. (eds.) Proceedings of STACS 2008, pp. 621\u2013632 (2008), \n                      http:\/\/stacs-conf.org\n                     (to appear in Theory of Computing Systems) arXiv:0802.2823v1"},{"issue":"5","key":"20_CR2","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1051\/ita\/1996300503791","volume":"30","author":"A. Weber","year":"1996","unstructured":"Weber, A.: Decomposing a k-valued transducer into k unambiguous ones. RAIRO Informatique Th\u00e9orique et Applications\u00a030(5), 379\u2013413 (1996)","journal-title":"RAIRO Informatique Th\u00e9orique et Applications"},{"key":"20_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1007\/978-3-540-85238-4_48","volume-title":"MFCS 2008","author":"J. Sakarovitch","year":"2008","unstructured":"Sakarovitch, J., Souza, R.: On the decidability of bounded valuedness for transducers. In: Ochma\u0144ski, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol.\u00a05162, pp. 588\u2013600. Springer, Heidelberg (2008), Preliminary full version with proofs in \n                      http:\/\/www.infres.enst.fr\/~rsouza\/DFV.pdf"},{"key":"20_CR4","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0304-3975(01)00214-6","volume":"292","author":"M.P. B\u00e9al","year":"2003","unstructured":"B\u00e9al, M.P., Carton, O., Prieur, C., Sakarovitch, J.: Squaring transducers: an efficient procedure for deciding functionality and sequentiality. Theoretical Computer Science\u00a0292, 45\u201363 (2003)","journal-title":"Theoretical Computer Science"},{"key":"20_CR5","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BF01744569","volume":"16","author":"E. Gurari","year":"1983","unstructured":"Gurari, E., Ibarra, O.: A note on finite-valued and finitely ambiguous transducers. Mathematical Systems Theory\u00a016, 61\u201366 (1983)","journal-title":"Mathematical Systems Theory"},{"issue":"1","key":"20_CR6","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/S0022-0000(68)80006-6","volume":"2","author":"P.C. Fischer","year":"1968","unstructured":"Fischer, P.C., Rosenberg, A.L.: Multitape one-way nonwriting automata. Journal of Computer and System Sciences\u00a02(1), 88\u2013101 (1968)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"20_CR7","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1145\/321466.321473","volume":"15","author":"T.V. Griffiths","year":"1968","unstructured":"Griffiths, T.V.: The unsolvability of the equivalence problem for \u039b-free nondeterministic generalized machines. Journal of the ACM\u00a015(3), 409\u2013413 (1968)","journal-title":"Journal of the ACM"},{"issue":"4","key":"20_CR8","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1137\/0207042","volume":"7","author":"O. Ibarra","year":"1978","unstructured":"Ibarra, O.: The unsolvability of the equivalence problem for \u03b5-free NGSM\u2019s with unary input (output) alphabet and applications. SIAM Journal on Computing\u00a07(4), 524\u2013532 (1978)","journal-title":"SIAM Journal on Computing"},{"key":"20_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/3-540-07407-4_22","volume-title":"Automata Theory and Formal Languages, 2nd GI Conference","author":"M.P. Sch\u00fctzenberger","year":"1975","unstructured":"Sch\u00fctzenberger, M.P.: Sur les relations rationnelles. In: Automata Theory and Formal Languages, 2nd GI Conference. LNCS, vol.\u00a033, pp. 209\u2013213. Springer, Heidelberg (1975)"},{"issue":"3","key":"20_CR10","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1016\/S0022-0000(77)80033-0","volume":"15","author":"M. Blattner","year":"1977","unstructured":"Blattner, M., Head, T.: Single-valued a-transducers. Journal of Computer and System Sciences\u00a015(3), 310\u2013327 (1977)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"20_CR11","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0304-3975(86)90134-9","volume":"47","author":"K. Culik","year":"1986","unstructured":"Culik, K., Karhum\u00e4ki, J.: The equivalence of finite valued transducers (on HDT0L languages) is decidable. Theoretical Computer Science\u00a047(1), 71\u201384 (1986)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"20_CR12","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1137\/0222014","volume":"22","author":"A. Weber","year":"1993","unstructured":"Weber, A.: Decomposing finite-valued transducers and deciding their equivalence. SIAM Journal on Computing\u00a022(1), 175\u2013202 (1993)","journal-title":"SIAM Journal on Computing"},{"key":"20_CR13","volume-title":"Computers and Intractability","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability. Freeman, New York (1979)"},{"issue":"2","key":"20_CR14","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0022-0000(81)90028-3","volume":"22","author":"E. Gurari","year":"1981","unstructured":"Gurari, E., Ibarra, O.: The complexity of decision problems for finite-turn multicounter machines. Journal of Computer and System Sciences\u00a022(2), 220\u2013229 (1981)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1\u20132","key":"20_CR15","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/S0304-3975(98)00040-1","volume":"204","author":"J. Sakarovitch","year":"1998","unstructured":"Sakarovitch, J.: A construction on finite automata that has remained hidden. Theoretical Computer Science\u00a0204(1\u20132), 205\u2013231 (1998)","journal-title":"Theoretical Computer Science"},{"issue":"8","key":"20_CR16","first-page":"749","volume":"27","author":"A. Weber","year":"1989","unstructured":"Weber, A.: On the valuedness of finite transducers. Acta Informatica\u00a027(8), 749\u2013780 (1989)","journal-title":"Acta Informatica"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Berstel, J.: Transductions and Context-Free Languages. B. G. Teubner (1979)","DOI":"10.1007\/978-3-663-09367-1"},{"key":"20_CR18","volume-title":"Automata, Languages, and Machines","author":"S. Eilenberg","year":"1974","unstructured":"Eilenberg, S.: Automata, Languages, and Machines, vol.\u00a0A. Academic Press, London (1974)"},{"key":"20_CR19","unstructured":"Sakarovitch, J.: \u00c9l\u00e9ments de th\u00e9orie des automates. Vuibert, Paris (2003); English translation: Elements of Automata Theory. Cambridge University Press, Cambridge (to appear)"},{"key":"20_CR20","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1142\/9789812703118_0015","volume-title":"Proc. of The Mathematical Foundations of Informatics (1999)","author":"J. Sakarovitch","year":"2005","unstructured":"Sakarovitch, J.: The rational skimming theorem. In: Van, D.L., Ito, M. (eds.) Proc. of The Mathematical Foundations of Informatics (1999), pp. 157\u2013172. World Scientific, Singapore (2005)"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85780-8_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,30]],"date-time":"2023-01-30T13:33:32Z","timestamp":1675085612000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-85780-8_20"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540857792","9783540857808"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85780-8_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008]]}}}