This paper extends the approach to feature structures developed in Johnson (1991a), which uses Schönfinkel-Bernays' formulae to express feature structure constraints. These are shown to be a disjunctive generalization of Datalog clauses, as used in database theory. This paper provides a fixed-point characterization of the minimal models of these formulae that serves as the theoretical foundation of a forward-chaining algorithm for determining their satisfiability. This algorithm, which generalizes the standard attribute-value unification algorithm, is also recognizable as a nondeterministic variant of the semi-naive bottom-up algorithm for evaluating Datalog programs, further strengthening the connection between the theory of feature structures and databases.
|Number of pages||26|
|Publication status||Published - Mar 1994|