Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo khoa học: "Factoring Synchronous Grammars By Sorting"

Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ

Synchronous Context-Free Grammars (SCFGs) have been successfully exploited as translation models in machine translation applications. When parsing with an SCFG, computational complexity grows exponentially with the length of the rules, in the worst case. In this paper we examine the problem of factorizing each rule of an input SCFG to a generatively equivalent set of rules, each having the smallest possible length. Our algorithm works in time O(n log n), for each rule of length n. This improves upon previous results and solves an open problem about recognizing permutations that can be factored. . | Factoring Synchronous Grammars By Sorting Daniel Gildea Computer Science Dept. University of Rochester Rochester NY 14627 Giorgio Satta Dept. of Information Eng g University of Padua I-35131 Padua Italy Hao Zhang Computer Science Dept. University of Rochester Rochester NY 14627 Abstract Synchronous Context-Free Grammars SCFGs have been successfully exploited as translation models in machine translation applications. When parsing with an SCFG computational complexity grows exponentially with the length of the rules in the worst case. In this paper we examine the problem of factorizing each rule of an input SCFG to a generatively equivalent set of rules each having the smallest possible length. Our algorithm works in time O n log n for each rule of length n. This improves upon previous results and solves an open problem about recognizing permutations that can be factored. 1 Introduction Synchronous Context-Free Grammars SCFGs are a generalization of the Context-Free Grammar CFG formalism to simultaneously produce strings in two languages. SCFGs have a wide range of applications including machine translation word and phrase alignments and automatic dictionary construction. Variations of SCFGs go back to Aho and Ullman 1972 s Syntax-Directed Translation Schemata but also include the Inversion Transduction Grammars in Wu 1997 which restrict grammar rules to be binary the synchronous grammars in Chiang 2005 which use only a single nonterminal symbol and the Multitext Grammars in Melamed 2003 which allow independent rewriting as well as other tree-based models such as Yamada and Knight 2001 and Galley et al. 2004 . When viewed as a rewriting system an SCFG generates a set of string pairs representing some translation relation. We are concerned here with the time complexity of parsing such a pair according to the grammar. Assume then a pair with each string having a maximum length of N and consider an SCFG G of size G with a bound of n nonterminals in the right-hand side .

TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.