{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:38:25Z","timestamp":1740123505679,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2015,9,21]],"date-time":"2015-09-21T00:00:00Z","timestamp":1442793600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada (CA)","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada (CA)","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada (CA)","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Machine Translation"],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1007\/s10590-015-9172-5","type":"journal-article","created":{"date-parts":[[2015,9,21]],"date-time":"2015-09-21T02:48:34Z","timestamp":1442803714000},"page":"163-187","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Complexity of alignment and decoding problems: restrictions and approximations"],"prefix":"10.1007","volume":"29","author":[{"given":"Noah","family":"Fleming","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonina","family":"Kolokolova","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Renesa","family":"Nizamee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,9,21]]},"reference":[{"issue":"2","key":"9172_CR1","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L Berman","year":"1977","unstructured":"Berman L, Hartmanis J (1977) On isomorphisms and density of NP and other complete sets. SIAM J Comput 6(2):305\u2013322","journal-title":"SIAM J Comput"},{"key":"9172_CR2","doi-asserted-by":"crossref","unstructured":"Birch A, Callison-Burch C, Osborne M, Koehn P (2006) Constraining the phrase-based, joint probability statistical translation model. In: HLT-NAACL 2006: proceedings of the workshop on statistical machine translation, New York, pp 154\u2013157","DOI":"10.3115\/1654650.1654675"},{"issue":"2","key":"9172_CR3","first-page":"263","volume":"19","author":"PF Brown","year":"1993","unstructured":"Brown PF, Della Pietra VJ, Della Pietra SA, Mercer RL (1993) The mathematics of statistical machine translation: parameter estimation. Comput Linguist 19(2):263\u2013311","journal-title":"Comput Linguist"},{"issue":"1","key":"9172_CR4","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1145\/1360443.1360454","volume":"39","author":"JF Buss","year":"2008","unstructured":"Buss JF, Islam TM (2008) The complexity of fixed-parameter problems: guest column. SIGACT News 39(1):33\u201346. doi: 10.1145\/1360443.1360454","journal-title":"SIGACT News"},{"key":"9172_CR5","unstructured":"Cesati M (2006) Compendium of parameterized problems. http:\/\/www.sprg.uniroma2.it\/home\/cesati\/research\/compendium\/compendium.pdf"},{"key":"9172_CR6","unstructured":"DeNero J (2010) Phrase alignment models for statistical machine translation. PhD Thesis, UC Berkeley, CA"},{"key":"9172_CR7","doi-asserted-by":"crossref","unstructured":"DeNero J, Klein D (2008) The complexity of phrase alignment problems. In: ACL-08: HLT. Proceedings of the 46th annual meeting of the association for computational linguistics on human language technologies: short papers, Columbus, pp 25\u201328","DOI":"10.3115\/1557690.1557698"},{"key":"9172_CR8","doi-asserted-by":"crossref","unstructured":"Downey RG, Fellows MR (1992) Fixed-parameter intractability. In: Proceedings of the seventh annual conference on structure in complexity theory, Victoria, pp 36\u201349","DOI":"10.1109\/SCT.1992.215379"},{"key":"9172_CR9","doi-asserted-by":"crossref","unstructured":"Feige U, Langberg M, Nissim K (2000) On the hardness of approximating NP witnesses. In: Approx 2000: approximation algorithms for combinatorial optimization. Proceedings of third international workshop. Lecture notes in computer science 1913. Springer, New York, pp 120\u2013131","DOI":"10.1007\/3-540-44436-X_13"},{"key":"9172_CR10","doi-asserted-by":"crossref","unstructured":"Gal A, Halevi S, Lipton RJ, Petrank E (1999) Computing from partial solutions. In: COCO \u201999: proceedings of the fourteenth annual IEEE conference on computational complexity, Atlanta, pp 34\u201345","DOI":"10.1109\/CCC.1999.766260"},{"key":"9172_CR11","unstructured":"Guruswami V, Rudra A (2008) Soft decoding, dual BCH codes, and better list-decodable $$\\varepsilon $$ \u03b5 -biased codes. In: CCC 2008: proceedings of the twenty-third annual IEEE conference on computational complexity, College Park, pp 163\u2013174"},{"key":"9172_CR12","unstructured":"Hamilton M, M\u00fcller M, van Rooij I, Wareham T (2007) Approximating solution structure. In: Demaine E, Gutin GZ, Marx D, Stege U (eds) Structure theory and FPT algorithmics for graphs, digraphs and hypergraphs, No. 07281 in Dagstuhl seminar proceedings. Internationales Begegnungs- und Forschungszentrum f\u00fcr Informatik (IBFI). Schloss Dagstuhl, Germany, Dagstuhl"},{"issue":"4","key":"9172_CR13","first-page":"607","volume":"25","author":"K Knight","year":"1999","unstructured":"Knight K (1999) Decoding complexity in word-replacement translation models. Comput Linguist 25(4):607\u2013615","journal-title":"Comput Linguist"},{"key":"9172_CR14","doi-asserted-by":"crossref","unstructured":"Koehn P (2004) Pharaoh: a beam search decoder for phrase-based statistical machine translation models. In: Machine translation: from real users to research: 6th conference of the Association for Machine Translation in the Americas. Springer, Berlin, pp 115\u2013124","DOI":"10.1007\/978-3-540-30194-3_13"},{"key":"9172_CR15","doi-asserted-by":"crossref","unstructured":"Koehn P, Och FJ, Marcu D (2003) Statistical phrase-based translation. In: HLT-NAACL 2003: conference combining human language technology conference series and the North American Chapter of the Association for Computational Linguistics conference series. Proceedings, Edmonton, pp 48\u201354","DOI":"10.3115\/1073445.1073462"},{"key":"9172_CR16","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn HW (1955) The Hungarian method for the assignment problem. Naval Res Logist Q 2:83\u201397","journal-title":"Naval Res Logist Q"},{"key":"9172_CR17","doi-asserted-by":"crossref","unstructured":"Kumar R, Sivakumar D (1999) Proofs, codes, and polynomial-time reducibilities. In: COCO \u201999: proceedings of the fourteenth annual IEEE conference on computational complexity, Atlanta, pp 46\u201353","DOI":"10.1109\/CCC.1999.766261"},{"issue":"3","key":"9172_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1380584.1380586","volume":"40","author":"A Lopez","year":"2008","unstructured":"Lopez A (2008) Statistical machine translation. ACM Comput Surv 40(3):1\u201349","journal-title":"ACM Comput Surv"},{"key":"9172_CR19","doi-asserted-by":"crossref","unstructured":"MacCartney B, Galley M, Manning CD (2008) A phrase-based alignment model for natural language inference. In: Proceedings of the conference on empirical methods in natural language processing. Association for Computational Linguistics, pp 802\u2013811","DOI":"10.3115\/1613715.1613817"},{"key":"9172_CR20","doi-asserted-by":"crossref","unstructured":"Marcu D, Wong W (2002) A phrase-based, joint probability model for statistical machine translation. In: EMNLP-2002: proceedings of the 2002 conference on empirical methods in natural language processing, Philadelphia, pp 133\u2013139","DOI":"10.3115\/1118693.1118711"},{"issue":"1","key":"9172_CR21","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1162\/089120103321337421","volume":"29","author":"FJ Och","year":"2003","unstructured":"Och FJ, Ney H (2003) A systematic comparison of various statistical alignment models. Comput Linguist 29(1):19\u201351","journal-title":"Comput Linguist"},{"issue":"3","key":"9172_CR22","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1162\/coli_a_00008","volume":"36","author":"S Ravi","year":"2010","unstructured":"Ravi S, Knight K (2010) Does giza++ make search errors? Comput Linguist 36(3):295\u2013302","journal-title":"Comput Linguist"},{"issue":"22","key":"9172_CR23","doi-asserted-by":"crossref","first-page":"685","DOI":"10.4086\/toc.2013.v009a022","volume":"9","author":"D Sheldon","year":"2013","unstructured":"Sheldon D, Young NE (2013) Hamming approximation of NP witnesses. Theory Comput 9(22):685\u2013702","journal-title":"Theory Comput"},{"key":"9172_CR24","doi-asserted-by":"crossref","unstructured":"S\u00f8gaard A (2009) On the complexity of alignment problems in two synchronous grammar formalisms. In: Proceedings of the third workshop on syntax and structure in statistical translation (SSST-3) at NAACL HLT 2009, Boulder, pp 60\u201368","DOI":"10.3115\/1626344.1626352"},{"key":"9172_CR25","unstructured":"Udupa R, Maji H (2005) Theory of alignment generators and applications to statistical machine translation. In: Proceedings of the 19th international joint conference on artificial intelligence, Edinburgh, pp 1142\u20131147"},{"key":"9172_CR26","unstructured":"Udupa R, Maji HK (2006) Computational complexity of statistical machine translation. In: EACL-2006: 11th conference of the European chapter of the Association for Computational Linguistics, proceedings of the conference, Trento, pp 25\u201332"},{"issue":"4","key":"9172_CR27","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1016\/j.jmp.2012.05.002","volume":"56","author":"I Rooij van","year":"2012","unstructured":"van Rooij I, Wareham T (2012) Intractability and approximation of optimization theories of cognition. J Math Psychol 56(4):232\u2013247","journal-title":"J Math Psychol"}],"container-title":["Machine Translation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10590-015-9172-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10590-015-9172-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10590-015-9172-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T14:37:47Z","timestamp":1559227067000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10590-015-9172-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,21]]},"references-count":27,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["9172"],"URL":"https:\/\/doi.org\/10.1007\/s10590-015-9172-5","relation":{},"ISSN":["0922-6567","1573-0573"],"issn-type":[{"type":"print","value":"0922-6567"},{"type":"electronic","value":"1573-0573"}],"subject":[],"published":{"date-parts":[[2015,9,21]]}}}