On the Decidability of Functional Uncertainty

ON THE DECIDABILITY OF FUNCTIONAL UNCERTAINTY* Rolf Backofen German Research Center for Artificial Intelligence (DFKI) W-6600 Saarbrficken, Germany backofen@dfki.uni-sb.de 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 un- certainty in two phases, both phases using a set of de- terministic and non-deterministic rewrite rules. We then compare our algorithm with the one of Kaplan and Maxwell, that does not cover cyclic feature de- scriptions. 1 Introduction Feature logic is the main device of unification gram- mars, the currently predominant paradigm in com- putational linguistics. More recently, feature de- scriptions have been proposed as a constraint system for logic programming (e.g. see [ll D . 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 vol- ume). We will follow the logical approach intro- duced 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 zfy, where x, y are first order vari- ables, 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 = fl-.. fn is a finite feature path. This does not affect the computational properties. In this paper we will be concerned with an ex- tension to feature descriptions, which has been in- troduced as "functional uncertainty" by Kaplan and Zaenen [7] and Kaplan and Maxwell [5]. This for- mal device plays an important role in the framework of LFG in modelling so-called long distance depen- dencies and constituent coordination. For a detailed linguistic motivation see [7], [6] and [5]; a more gen- eral use of functional uncertainty can be found in [8]. Functional uncertainty consists of constraints of *This work was supported by a research grant, ITW 9002 0, from the German Bundesministerium ffir Forschung und Technologic to the DFKI project DISCO. I would like to thank Jochen Dhrre, Joachim Niehren and Ralf Treinen for reading draft version of this paper. For space limitations most of the proofs are omitted; they can be found in the complete paper [2] the form xLy, where L is a finite description of a regular language of feature paths. A constraint xLy holds if there is a path w E L such that zwy holds. Under this existential interpretation, a con- straint xLy can be seen as the disjunction = I ,.,, e xLy L}. Certainly, this disjunction may be infinite, thus functional uncertainty yields additional expressivity. Note that a constraint zwy is a special case of a func- tional uncertainty constraint. To see some possible application of functional un- certainty we briefly recall an example …

Content truncated to 500 words