Computing with features as formulae

Research output: Contribution to journalArticlepeer-review

17 Downloads (Pure)


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.
Original languageEnglish
Pages (from-to)1-26
Number of pages26
JournalComputational Linguistics
Issue number1
Publication statusPublished - Mar 1994
Externally publishedYes

Bibliographical note

Copyright the Publisher 1994. Version archived for private and non-commercial use with the permission of the author/s and according to publisher conditions. For further rights please contact the publisher.


Dive into the research topics of 'Computing with features as formulae'. Together they form a unique fingerprint.

Cite this