Computing with features as formulae

Mark Johnson

Computing with features as formulae

Research output: Contribution to journal › Article › peer-review

23 Downloads (Pure)

Abstract

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 language	English
Pages (from-to)	1-26
Number of pages	26
Journal	Computational Linguistics
Volume	20
Issue number	1
Publication status	Published - Mar 1994
Externally published	Yes

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.

Access to Document

Publisher version (open access)Final published version, 1.41 MBLicence: CC BY-NC-SA

https://www.aclweb.org/anthology/J94-1001/Licence: CC BY-NC-SA

Cite this

@article{d3fa10a93ae4478d8161b866b2877a83,

title = "Computing with features as formulae",

abstract = "This paper extends the approach to feature structures developed in Johnson (1991a), which uses Sch{\"o}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. ",

author = "Mark Johnson",

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. ",

year = "1994",

month = mar,

language = "English",

volume = "20",

pages = "1--26",

journal = "Computational Linguistics",

issn = "0891-2017",

publisher = "MIT Press Journals",

number = "1",

}

TY - JOUR

T1 - Computing with features as formulae

AU - Johnson, Mark

N1 - 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.

PY - 1994/3

Y1 - 1994/3

N2 - 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.

AB - 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.

M3 - Article

SN - 0891-2017

VL - 20

SP - 1

EP - 26

JO - Computational Linguistics

JF - Computational Linguistics

IS - 1

ER -

Computing with features as formulae

Abstract

Bibliographical note

Access to Document

Fingerprint

Cite this