Expressing disjunctive and negative feature constraints with classical first-order logic

Mark Johnson

doi:10.3115/981823.981845

Expressing disjunctive and negative feature constraints with classical first-order logic

Mark Johnson

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

5 Citations (Scopus)

38 Downloads (Pure)

Abstract

In contrast to the "designer logic" approach, this paper shows how the attribute-value feature structures of unification grammar and constraints on them can be axiomatized in classical first-order logic, which can express disjunctive and negative constraints. Because only quantifier-free formulae are used in the axiomatization, the satisfiability problem is NP-complete.

Original language	English
Title of host publication	Proceedings of the 28th Annual Meeting of the Association for Computational Linguistics
Place of Publication	Morristown, NJ
Publisher	Association for Computational Linguistics
Pages	173-179
Number of pages	7
DOIs	https://doi.org/10.3115/981823.981845
Publication status	Published - 1990
Externally published	Yes
Event	Annual Meeting of the Association for Computational Linguistics (28th : 1990) - University of Pittsburgh, Pittsburgh, United States Duration: 6 Jun 1990 → 9 Jun 1990

Conference

Conference	Annual Meeting of the Association for Computational Linguistics (28th : 1990)
Country/Territory	United States
City	Pittsburgh
Period	6/06/90 → 9/06/90

Bibliographical note

Copyright the Publisher 1990. 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

10.3115/981823.981845

Publisher version (open access)Final published version, 324 KBLicence: CC BY-NC-SA

Cite this

@inproceedings{ef8af420d947496d8477eee07991c096,

title = "Expressing disjunctive and negative feature constraints with classical first-order logic",

abstract = "In contrast to the {"}designer logic{"} approach, this paper shows how the attribute-value feature structures of unification grammar and constraints on them can be axiomatized in classical first-order logic, which can express disjunctive and negative constraints. Because only quantifier-free formulae are used in the axiomatization, the satisfiability problem is NP-complete.",

author = "Mark Johnson",

note = "Copyright the Publisher 1990. 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. ; Annual Meeting of the Association for Computational Linguistics (28th : 1990) ; Conference date: 06-06-1990 Through 09-06-1990",

year = "1990",

doi = "10.3115/981823.981845",

language = "English",

pages = "173--179",

booktitle = "Proceedings of the 28th Annual Meeting of the Association for Computational Linguistics",

publisher = "Association for Computational Linguistics",

}

Johnson, M 1990, Expressing disjunctive and negative feature constraints with classical first-order logic. in Proceedings of the 28th Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics, Morristown, NJ, pp. 173-179, Annual Meeting of the Association for Computational Linguistics (28th : 1990), Pittsburgh, Pennsylvania, United States, 6/06/90. https://doi.org/10.3115/981823.981845

Expressing disjunctive and negative feature constraints with classical first-order logic. / Johnson, Mark.
Proceedings of the 28th Annual Meeting of the Association for Computational Linguistics. Morristown, NJ: Association for Computational Linguistics, 1990. p. 173-179.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Expressing disjunctive and negative feature constraints with classical first-order logic

AU - Johnson, Mark

N1 - Copyright the Publisher 1990. 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 - 1990

Y1 - 1990

N2 - In contrast to the "designer logic" approach, this paper shows how the attribute-value feature structures of unification grammar and constraints on them can be axiomatized in classical first-order logic, which can express disjunctive and negative constraints. Because only quantifier-free formulae are used in the axiomatization, the satisfiability problem is NP-complete.

AB - In contrast to the "designer logic" approach, this paper shows how the attribute-value feature structures of unification grammar and constraints on them can be axiomatized in classical first-order logic, which can express disjunctive and negative constraints. Because only quantifier-free formulae are used in the axiomatization, the satisfiability problem is NP-complete.

UR - https://www.aclweb.org/anthology/P90-1022/

U2 - 10.3115/981823.981845

DO - 10.3115/981823.981845

M3 - Conference proceeding contribution

SP - 173

EP - 179

BT - Proceedings of the 28th Annual Meeting of the Association for Computational Linguistics

PB - Association for Computational Linguistics

CY - Morristown, NJ

T2 - Annual Meeting of the Association for Computational Linguistics (28th : 1990)

Y2 - 6 June 1990 through 9 June 1990

ER -

Expressing disjunctive and negative feature constraints with classical first-order logic

Abstract

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this