TAILIEUCHUNG - Báo cáo khoa học: "Transforming Lattices into Non-deterministic Automata with Optional Null Arcs"

The problem of transforming a lattice into a non-deterministic finite state automaton is non-trivial. We present a transformation algorithm which tracks, for each node of an automaton under construction, the larcs which it reflects and the lattice nodes at their origins and extremities. An extension of the algorithm permits the inclusion of null, or epsilon, arcs in the output automaton. The algorithm has been successfully applied to lattices derived from dictionaries, . very large corpora of strings. . | Transforming Lattices into Non-deterministic Automata with Optional Null Arcs Mark Seligman Christian Boitet Boubaker Meddeb-Hamrouni Université Joseph Fourier GETA CLIPS IMAG-campus BP 53 150 rue de la Chimie 38041 Grenoble Cedex 9 France seligman@ @imag. fr Abstract The problem of transforming a lattice into a non-deterministic finite state automaton is non-trivial. We present a transformation algorithm which tracks for each node of an automaton under construction the lares which it reflects and the lattice nodes at their origins and extremities. An extension of the algorithm permits the inclusion of null or epsilon arcs in the output automaton. The algorithm has been successfully applied to lattices derived from dictionaries . very large corpora of strings. Introduction Linguistic data grammars speech recognition results etc. are sometimes represented as lattices and sometimes as equivalent finite state automata. While the transformation of automata into lattices is straightforward we know of no algorithm in the current literature for transforming a lattice into a non-deterministic finite state automaton. See . Hopcroft et al 1979 Aho et al 1982 . We describe such an algorithm here. Its main feature is the maintenance of complete records of the relationships between objects in the input lattice and their images on an automaton as these are added during transformation. An extension of the algorithm permits the inclusion of null or epsilon arcs in the output automaton. The method we present is somewhat complex but we have thus far been unable to discover a simpler one. One suggestion illustrates the difficulties this proposal was simply to slide lattice node labels leftward onto their incoming arcs and then starting with the final lattice node to merge nodes with identical outgoing arc sets. This strategy does successfully transform many lattices but fails on lattices like this one For this lattice the .

• Báo cáo khoa học
• Transforming Lattices
• Non deterministic Automata
• Optional Null Arcs
• 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