{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T18:14:00Z","timestamp":1725732840111},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642387081"},{"type":"electronic","value":"9783642387098"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44602-7_12","type":"book-chapter","created":{"date-parts":[[2014,8,23]],"date-time":"2014-08-23T01:18:40Z","timestamp":1408756720000},"page":"136-150","source":"Crossref","is-referenced-by-count":1,"title":["Not All Multi-Valued Partial CFL Functions Are Refined by Single-Valued Functions (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Tomoyuki","family":"Yamakami","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1137\/0212019","volume":"12","author":"C. Choffrut","year":"1983","unstructured":"Choffrut, C., Culik, K.: Properties of finite and pushdown transducers. SIAM J. Comput.\u00a012, 300\u2013315 (1983)","journal-title":"SIAM J. Comput."},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Evey, R.J.: Application of pushdown-store machines. In: Proc. 1963 Fall Joint Computer Conference, pp. 215\u2013227. AFIPS Press (1963)","DOI":"10.1145\/1463822.1463848"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Fisher, P.C.: On computability by certain classes of restricted Turing machines. In: Proc. 4th Annual IEEE Symp. on Switching Circuit Theory and Logical Design (SWCT 1963), pp. 23\u201332. IEEE Computer Society (1963)","DOI":"10.1109\/SWCT.1963.10"},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison-Wesley (2001)","DOI":"10.1145\/568438.568455"},{"key":"12_CR5","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/S0019-9958(69)90651-2","volume":"15","author":"K. Kobayashi","year":"1969","unstructured":"Kobayashi, K.: Classification of formal langauges by functional binary transductions. Inform. Control\u00a015, 95\u2013109 (1969)","journal-title":"Inform. Control"},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/s00236-006-0027-7","volume":"43","author":"S. Konstantinidis","year":"2007","unstructured":"Konstantinidis, S., Santean, N., Yu, S.: Representation and uniformization of algebraic transductions. Acta Inform.\u00a043, 395\u2013417 (2007)","journal-title":"Acta Inform."},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/S0022-0000(05)80009-1","volume":"48","author":"A.L. Selman","year":"1994","unstructured":"Selman, A.L.: A taxonomy of complexity classes of functions. J. Comput. System Sci.\u00a048, 357\u2013381 (1994)","journal-title":"J. Comput. System Sci."},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"Selman, A.L.: Much ado about functions. In: Proc. of the 11th Annual IEEE Conference on Computational Complexity, pp. 198\u2013212 (1996)","DOI":"10.1109\/CCC.1996.507682"},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.tcs.2009.08.031","volume":"411","author":"K. Tadaki","year":"2010","unstructured":"Tadaki, K., Yamakami, T., Lin, J.C.H.: Theory of one-tape linear-time Turing machines. Theoret. Comput. Sci.\u00a0411, 22\u201343 (2010)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR10","unstructured":"Yamakami, T.: Swapping lemmas for regular and context-free languages (2008), Available at arXiv:0808.4122"},{"key":"12_CR11","unstructured":"Yamakami, T.: Pseudorandom generators against advised context-free languages (2009), See arXiv:0902.2774"},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"6432","DOI":"10.1016\/j.tcs.2011.07.013","volume":"412","author":"T. Yamakami","year":"2011","unstructured":"Yamakami, T.: Immunity and pseudorandomness of context-free languages. Theor. Comput. Sci.\u00a0412, 6432\u20136450 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1007\/978-3-319-04298-5_45","volume-title":"SOFSEM 2014: Theory and Practice of Computer Science","author":"T. Yamakami","year":"2014","unstructured":"Yamakami, T.: Oracle pushdown automata, nondeterministic reducibilities, and the hierarchy over the family of context-free languages. In: Geffert, V., Preneel, B., Rovan, B., \u0160tuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol.\u00a08327, pp. 514\u2013525. Springer, Heidelberg (2014)"},{"key":"12_CR14","unstructured":"Yamakami, T.: Structural complexity of multi-valued partial functions computed by nondeterministic pushdown automata (2014) (unpublished manuscript)"}],"container-title":["Lecture Notes in Computer Science","Advanced Information Systems Engineering"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44602-7_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,14]],"date-time":"2019-08-14T06:36:46Z","timestamp":1565764606000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44602-7_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783642387081","9783642387098"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44602-7_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}