{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:08Z","timestamp":1760202668602},"reference-count":51,"publisher":"MIT Press","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2014,9]]},"abstract":"<jats:p>This article describes the use of pushdown automata (PDA) in the context of statistical machine translation and alignment under a synchronous context-free grammar. We use PDAs to compactly represent the space of candidate translations generated by the grammar when applied to an input sentence. General-purpose PDA algorithms for replacement, composition, shortest path, and expansion are presented. We describe HiPDT, a hierarchical phrase-based decoder using the PDA representation and these algorithms. We contrast the complexity of this decoder with a decoder based on a finite state automata representation, showing that PDAs provide a more suitable framework to achieve exact decoding for larger synchronous context-free grammars and smaller language models. We assess this experimentally on a large-scale Chinese-to-English alignment and translation task. In translation, we propose a two-pass decoding strategy involving a weaker language model in the first-pass to address the results of PDA complexity analysis. We study in depth the experimental conditions and tradeoffs in which HiPDT can achieve state-of-the-art performance for large-scale SMT.<\/jats:p>","DOI":"10.1162\/coli_a_00197","type":"journal-article","created":{"date-parts":[[2014,3,28]],"date-time":"2014-03-28T23:10:37Z","timestamp":1396048237000},"page":"687-723","source":"Crossref","is-referenced-by-count":7,"title":["Pushdown Automata in Statistical Machine Translation"],"prefix":"10.1162","volume":"40","author":[{"given":"Cyril","family":"Allauzen","sequence":"first","affiliation":[{"name":"Google Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bill","family":"Byrne","sequence":"additional","affiliation":[{"name":"University of Cambridge"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adri\u00e0","family":"de Gispert","sequence":"additional","affiliation":[{"name":"University of Cambridge"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gonzalo","family":"Iglesias","sequence":"additional","affiliation":[{"name":"University of Cambridge"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Riley","sequence":"additional","affiliation":[{"name":"Google Research"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","reference":[{"key":"R1","volume-title":"The Theory of Parsing, Translation and Compiling","volume":"1","author":"Aho Alfred V.","year":"1972"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-18098-9_4"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-76336-9_3"},{"key":"R5","first-page":"116","volume-title":"Language and Information: Selected Essays on their Theory and Application.","author":"Bar-Hillel Y.","year":"1964"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-09367-1"},{"key":"R7","first-page":"27","volume-title":"Proceedings of the ACL: Short Papers","author":"Blackwood Graeme","year":"2010"},{"key":"R8","first-page":"858","volume-title":"Proceedings of EMNLP-ACL","author":"Brants Thorsten","year":"2007"},{"key":"R9","first-page":"26","volume-title":"Proceedings of EMNLP","author":"Chang Yin-Wen","year":"2011"},{"key":"R10","first-page":"2,242","volume-title":"Proceedings of Interspeech","author":"Chelba Ciprian","year":"2010"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1162\/coli.2007.33.2.201"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1162\/coli_a_00006"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1109\/TASL.2008.916056"},{"key":"R14","unstructured":"Dyer, Chris. 2010a. A Formal Model of Ambiguity and its Applications in Machine Translation. Ph.D. thesis, University of Maryland."},{"key":"R15","first-page":"263","volume-title":"Proceedings of NAACL-HLT","author":"Dyer Chris","year":"2010"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.21236\/ADA460212"},{"key":"R17","first-page":"646","volume-title":"Proceedings of EMNLP","author":"Hopkins M.","year":"2010"},{"key":"R18","first-page":"1","volume-title":"Proceedings of COLING","author":"Huang Liang","year":"2008"},{"key":"R19","first-page":"144","volume-title":"Proceedings of ACL","author":"Huang Liang","year":"2007"},{"key":"R20","first-page":"273","volume-title":"Proceedings of EMNLP","author":"Huang Liang","year":"2010"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.3115\/1654494.1654501"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.3115\/1620754.1620817"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.3115\/1609067.1609109"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1987.1165125"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.1995.479394"},{"key":"R26","first-page":"1,288","volume-title":"Proceedings of EMNLP","author":"Koo Terry","year":"2010"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69959-7"},{"key":"R28","first-page":"169","volume-title":"Proceedings of HLT-NAACL","author":"Kumar Shankar","year":"2004"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.3115\/1220575.1220596"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1017\/S1351324905003815"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21545-6_18"},{"key":"R32","doi-asserted-by":"crossref","first-page":"1,251","DOI":"10.21437\/Eurospeech.1999-293","volume-title":"Proceedings of Eurospeech","author":"Ljolje Andrej","year":"1999"},{"key":"R33","first-page":"321","volume":"7","author":"Mohri Mehryar","year":"2002","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01492-5_6"},{"key":"R35","first-page":"137","volume-title":"Proceedings of 8th International Workshop on Parsing Technologies","author":"Nederhof Mark-Jan","year":"2003"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147959"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.3115\/1075096.1075117"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01492-5_7"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1109\/PORTABLE.2007.23"},{"key":"R40","first-page":"43","volume-title":"Proceedings of ACL","author":"Roark Brian","year":"2013"},{"key":"R41","first-page":"1","volume-title":"Proceedings of ACL-HLT","author":"Roark Brian","year":"2011"},{"key":"R42","first-page":"72","volume-title":"Proceedings of ACL-HLT","author":"Rush Alexander M.","year":"2011"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.3115\/1220575.1220676"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1109\/ASRU.2011.6163945"},{"issue":"2","key":"R45","first-page":"165","volume":"21","author":"Stolcke Andreas","year":"1995","journal-title":"Computational Linguistics"},{"key":"R46","first-page":"270","volume-title":"Proceedings of DARPA Broadcast News Transcription and Understanding Workshop","author":"Stolcke Andreas","year":"1998"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.3115\/1613715.1613792"},{"key":"R48","first-page":"377","volume":"23","author":"Wu Dekai","year":"1997","journal-title":"Computational Linguistics"},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.3115\/1699510.1699558"},{"key":"R50","first-page":"195","volume-title":"Proceedings of IWSLT","author":"Zens Richard","year":"2008"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.3115\/1220835.1220868"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.3115\/1654650.1654671"}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/COLI_a_00197","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,11]],"date-time":"2023-07-11T16:32:02Z","timestamp":1689093122000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/40\/3\/687-723\/1481"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,9]]}},"alternative-id":["10.1162\/COLI_a_00197"],"URL":"https:\/\/doi.org\/10.1162\/coli_a_00197","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9]]}}}