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