TAILIEUCHUNG - Báo cáo khoa học: "On the Equivalence of Weighted Finite-state Transducers"

Although they can be topologically different, two distinct transducers may actually recognize the same rational relation. Being able to test the equivalence of transducers allows to implement such operations as incremental minimization and iterative composition. | On the Equivalence of Weighted Finite-state Transducers Julien Quint National Institute of Informatics Hitotsubashi 2-1-2 Chiyoda-ku Tokyo 101-8430 Japan quint@ Abstract Although they can be topologically different two distinct transducers may actually recognize the same rational relation. Being able to test the equivalence of transducers allows to implement such operations as incremental minimization and iterative composition. This paper presents an algorithm for testing the equivalence of deterministic weighted finite-state transducers and outlines an implementation of its applications in a prototype weighted finite-state calculus tool. Introduction The addition of weights in finite-state devices where transitions initial states and final states are weighted introduced the need to reevaluate many of the techniques and algorithms used in classical finite-state calculus. Interesting consequences are for instance that not all non-deterministic weighted automata can be made deterministic Buchsbaum et al. 2000 or that epsilon transitions may offset the weights in the result of the composition of two transducers Pereira and Riley 1997 . A fundamental operation on finite-state transducers in equivalence testing which leads to applications such as incremental minimization and iterative composition. Here we present an algorithm for equivalence testing in the weighted case and describe its application to these applications. We also describe a prototype implementation which is demonstrated. 1 Definitions We define a weighted finite-state automata WFST T over a set of weights K by an 8-tuple s Q Q I F E X p where s and Q are two finite sets of symbols alphabets Q is a finite set of states I c Q is the set of initial states F c Q is the set of final states E c QxXu e xQu e xKxQ is the set of transitions and X I K and p F K are the initial and final weight functions. A transition e E E has a label l e E Su e xQu e a weight w e E K and a destination ỗ e E Q. The set of

• Báo cáo khoa học
• On the Equivalence of Weighted
• Finite state Transducers
• Julien Quint
• báo cáo khoa học
• mô hình ngôn ngữ
• xử lý ngôn ngữ tự nhiên
• Bài giảng Xử lý ngôn ngữ tự nhiên
• Ngôn ngữ tự nhiên
• Kỹ thuật lập trình
• Xử lý nhập nhằng ngữ nghĩa
• Xử lý ngữ nghĩa
• Xử lý ngôn ngữ
• Natural Language Processing
• Ngôn ngữ lập trình
• Nhập nhằng cấu trúc
• Tri thức về ngôn ngữ
• Mô hình n gram
• Dịch máy
• Phương pháp dịch máy
• Hiểu ngôn ngữ
• Phân tích ngữ nghĩa
• Phân loại tin tự động
• Biểu diễn vị từ
• Thuộc tính về sự kiện
• Thuộc tính về sự kiện
• Mô hình ngôn ngữ Google Book N grams
• Mô hình ngôn ngữ KenLM
• Phương pháp làm mịn
• Tách từ tiếng Việt
• Gán nhãn từ loại
• Phân tích cú pháp
• Nghĩa từ vựng
• Phân giải nhập nhằng từ
• Phân loại văn bản
• Lexical chain
• Phản hồi thông tin
• Bài toán PTCP
• Cấu trúc ngữ pháp
• Phân tích cú pháp xác suất
• CKY kết hợp xác suất
• Văn phạm phi ngữ cảnh xác suất
• Hình thái học