tailieunhanh - Báo cáo khoa học: "ON THE DECIDABILITY OF FUNCTIONAL UNCERTAINTY*"

We show that feature logic extended by functional uncertainty is decidable, even if one admits cyclic descriptions. We present an algorithm, which solves feature descriptions containing functional uncertainty in two phases, both phases using a set of deterministic and non-deterministic rewrite rules. We then compare our algorithm with the one of Kaplan and Maxwell, that does not cover cyclic feature descriptions. 1 Introduction the form x L y , where L is a finite description of a regular language of feature paths. A constraint x L y holds if there is a path w E L such that z. | ON THE DECIDABILITY OF FUNCTIONAL UNCERTAINTY Rolf Backofen German Research Center for Artificial Intelligence DFKI W-6600 Saarbrucken Germany backofen@ Abstract We show that feature logic extended by functional uncertainty is decidable even if one admits cyclic descriptions. We present an algorithm which solves feature descriptions containing functional uncertainty in two phases both phases using a set of deterministic and non-deterministic rewrite rules. We then compare our algorithm with the one of Kaplan and Maxwell that does not cover cyclic feature descriptions. 1 Introduction Feature logic is the main device of unification grammars the currently predominant paradigm in computational linguistics. More recently feature descriptions have been proposed as a constraint system for logic programming . see 11 . They provide for partial descriptions of abstract objects by means of functional attributes called features. Formalizations of feature logic have been proposed in various forms for more details see 3 in this volume . We will follow the logical approach introduced by Smolka 9 10 where feature descriptions are standard first order formulae interpreted in first order structures. In this formalization features are considered as functional relations. Atomic formulae which we will call atomic constraints are of either the form A x or xfy where X y are first order variables A is some sort predicate and f is a feature written in infix notation . The constraints of the form xfy can be generalized to constraints of the form xwy where w is a finite feature path. This does not affect the computational properties. In this paper we will be concerned with an extension to feature descriptions which has been introduced as functional uncertainty by Kaplan and Zaenen 7 and Kaplan and Maxwell 5 . This formal device plays an important role in the framework of LFG in modelling so-called long distance dependencies and constituent coordination. For a detailed

• Báo cáo khoa học
• ON THE DECIDABILITY
• FUNCTIONAL UNCERTAINTY
• Rolf Backofen
• báo cáo khoa học
• mô hình ngôn ngữ
• xử lý ngôn ngữ tự nhiên
• Decidability and Undecidability
• stand alone Feature Logics
• Patrick Blackburn
• scientific reports
• model language
• process natural language
• Theory of Computation
• Lecture Theory of Computation
• Logical theories
• Decidability of logical theories
• Presburger arithmetic
• Decidability of presburger arithmetic
• 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