Feature Structures ------- ---------- Information can be encoded in `feature structures', which are rooted labeled graphs. To explain, a feature structure is a set of graph nodes (points), a set of directed edges between pairs of nodes (arrows), and an assignment of labels (symbols of some kind) to SOME of the nodes and ALL of the arrows. No node may be the source of two arrows with the same label. One of the nodes is distinguished as the root node, and all of the nodes are reachable from the root by following the directed edges (going only in the direction of the arrows). An example feature structure is CATEGORY HEAD * -----------> cat ------> noun ------> nominative \ \ \ \ SUBCAT \ +------> empty-list \ \ CONTENT INDEX PERSON +-------> ppro -----> ref ------> 3rd |\ | \ NUMBER | +------> singular | | GENDER +---------> feminine This is part of the dictionary entry for the word `she' for a typical computer English parser. Feature struct- ures seem to be the most natural way to describe lin- guistic information and grammar rules, and because of this, it is conceivable that the human mind uses some analog of feature structures to parse sentences. From now on we will use single upper case characters as arrow labels, and single decimal digits as node labels. Unlabeled nodes will be represented by `#', and the root node will be marked by `*'. With this in mind, consider the feature structure A B E #* ---------> # ------>9 -----+ \ ^ | \ C D | | +--------> 4 -------+ | ^ | | | +---------------+ A path from the root to a node N in feature structure is a list of edges starting at the root and going to N, where the target of one edge is the source of the next edge. A path can be named by giving the edge labels in sequence, which we do separated by dots, with an initial dot added to make it easy to distinguish the empty path that names the root. A path is said to name the target of its last edge. Thus in the above example, `.' names the root node, `.A' names the other unlabeled node, and `.A.B' and `.C.D' name the node with value `9'. Actual- ly this node has an infinite number of names, including `.A.B.E.D' and `.C.D.E.D.E.D'. A feature structure can be described by a set of equa- tions. Let P, P1, P2 be a path names, and V be a node value. Then the equations have one of three forms: P P:V P1=P2 The equation P means a node named P exists. The equa- tion P:V means a node named P exists and is labeled with the value V (we will say the node `has value V'). The equation P1=P2 means there exists a node that has both the name P1 and the name P2. Our example feature structure can be described by the equations .A.B:9 .C:4 .C.D=.A.B .C.D.E=.C These are not the only equations true for the this feature structure, but the example feature structure is the smallest feature structure that satisfies these equations, in a sense we will now make precise. As feature structures store information, we might expect them to have a notion of one feature structure having more information than another. If F1 and F2 are feature structures, we say `F1 <= F2' (here <= means `is greater than', or `has more information than') if and only if every equation true of F1 is also true of F2. Thus F1 is more general than F2, and F2 is more specific than F1. The technical term for this is that `F1 subsumes F2', where `subsumes' just means `is more general than'. What does `F1 <= F2' mean in terms of rooted directed labeled graphs. It means (1) for every node in F1 named by some path P, there is a node in F2 with name P; (2) for every node in F1 named by some path P that has value V, the node in F2 named by P also has value V; and (3) if some node in F1 has both names P1 and P2, then the node named P1 in F2 also has name P2. As a consequence of all this there is a map of nodes of F1 to nodes of F2 such that (1) a node named P in F1 is mapped to a node named P in F2, and (2) if a node in F1 has value V, the node it is mapped to in F2 also has value V. The property of feature structures that makes them ex- tremely useful in computing is that certain computations of feature structures have a minimum answer: that is, a feature structure can be computed that is smaller than any other suitable feature structure. One instance of this is the following: given a set of equations, either there is no feature structure satisfy- ing all the equations, or there is exactly one minimum feature structure satisfying all the equations. If there is no feature structure satisfying the equations, then the equations are said to be incompatible. For example, the equations .A:1 .A.B=.A .A.B:2 are incompatible, because they imply there is a node with both the names .A and .A.B, which is fine, but also this node has both values 1 and 2, which is not allowed: no node may have more than one label. Two feature structures F1 and F2 are said to be compa- tible if and only if there is some feature structure F such that F1 <= F and F2 <= F. Then there is a minimum F, which is just the minimum F satisfying all the equa- tions of F1 and all the equations of F2. This is very useful, because if a computer knows that F1 and F2 are true, it does not have to keep both F1 and F2 around: instead it can compute the minimum F and keep that for future computations. This greatly improves the effi- ciency of the computation, and is the reason that feature structures are a good way for a computer to represent information. To compute the minimum feature structure satisfying a set of equations, proceed to add one equation at a time. Start with the feature structure F equal to `*#', which is just an unlabeled root node. Given a new equation P, just add nodes and arrows as necessary to F until a node named P exists. Any nodes added have no value. Given a new equation P:V, make a node named P if none exists, and then give that node the value V. If a node named P already exists and already has a value DIFFERENT from V, the equations are incompatible. Given a new equation P1=P2, make nodes named P1 and P2 if necessary, and then merge them to make a single node. Merging nodes means gluing them together so that they are the same node. If you must merge nodes that have DIFFERENT values, the equations are incompatible. Computationally N1 and N2 can be merged by storing in N1 a forwarding pointer to N2; this forwarding pointer behaves like a forwarding address in a mail system. When you merge nodes N1 and N2, you keep all the arrows from BOTH nodes, BUT if X X if N1--->N1' and N2--->N2' you must merge N1' and N2'. That is, if two nodes being merged are BOTH sources for an arrow labeled X, you keep just one of the arrows but you merge the destinations of the arrows. So merging is a recursive operation. In this problem you are given sets of equations and are asked to compute for each set the minimum feature struc- ture described and answer questions about it. Input ----- For each of several cases, A line containing only `EQUATIONS'. Zero or more lines each containing an equation. All these equations together describe a minimum feature structure. A line containing only `QUESTIONS'. Zero or more lines each containing an equation to be tested against the minimum feature structure. A line containing only `DONE'. There are no spaces in any input line. The equations are as described above. No equation is more than 80 characters long. Input ends with an end of file. Output ------ For each case, A line containing `Case #' where # is 1, 2, 3, ..., the case number. If the EQUATIONS are incompatible, a single line containing `INCOMPATIBLE'. Otherwise, for each QUESTION in order, a single line containing either `TRUE' or `FALSE', that tells whether the QUESTION is true of the minimal feature structure that satisfies the EQUATIONS. Example Input ------- ----- EQUATIONS .A .B .B:6 QUESTIONS .A .B .C .A:3 .B:6 DONE EQUATIONS .A.B:9 .C:4 .C.D=.A.B .C.D.E=.C QUESTIONS .A:3 .A .C.D:8 .C.D.E.D:9 .A.B.E.D=.C .A.B.E=.C .A.B.E:4 .A.B.E:9 .A.E DONE EQUATIONS .A:1 .A.B:2 .A.B=.A QUESTIONS DONE Example Output ------- ------ Case 1: TRUE TRUE FALSE FALSE TRUE Case 2: FALSE TRUE FALSE TRUE FALSE TRUE TRUE FALSE FALSE Case 3: INCOMPATIBLE Reference --------- Bob Carpenter, The Logic of Typed Feature Structures, Cambridge University Press, 1992. File: features.txt Author: Bob Walton Date: Sun Oct 19 08:16:33 EDT 2003 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file. RCS Info (may not be true date or author): $Author: walton $ $Date: 2003/10/19 12:17:22 $ $RCSfile: features.txt,v $ $Revision: 1.9 $