Article

Free access

Unification of disjunctive feature descriptions

Authors:

Andreas Eisele,

Jochen DörreAuthors Info & Claims

ACL '88: Proceedings of the 26th annual meeting on Association for Computational Linguistics

Pages 286 - 294

https://doi.org/10.3115/982023.982058

Published: 07 June 1988 Publication History

Abstract

The paper describes a new implementation of feature structures containing disjunctive values, which can be characterized by the following main points: Local representation of embedded disjunctions, avoidance of expansion to disjunctive normal form and of repeated test-unifications for checking consistence. The method is based on a modification of Kasper and Rounds' calculus of feature descriptions and its correctness therefore is easy to see. It can handle cyclic structures and has been incorporated successfully into an environment for grammar development.

References

[1]

{Aït-Kaci/Nasr 86} Aït-Kaci, H. and R. Nasr (1986). LOGIN: A Logic Programming Language with Built-In Inheritance. The Journal of Logic Programming, 1986 (3).

Digital Library

[2]

{Bear 87} Bear, J. (1987). Feature-Value Unification with Disjunctions. Ms. SRI International, Stanford, CA.

[3]

{Eisele 87} Eisele, A. (1987). Eine Implementierung rekursiver Merkmalstrukturen mit disjunktiven Angaben. Diplomarbeit. Institut f. Informatik, Stuttgart.

[4]

{Eisele/Dörre 86} Eisele, A. and J. Dörre (1986). A Lexical Functional Grammar System in Prolog. In: Proceedings of COLING 1986, Bonn.

Digital Library

[5]

{Eisele/Schimpf 87} Eisele, A. and S. Schimpf (1987). Eine benutzerfreundliche Softwareumgebung zur Entwicklung von LFGen. Studienarbeit. IfI, Stuttgart.

[6]

{Gazdar et al. 85} Gazdar, G., E. Klein, G. Pullum and I. Sag (1985). Generalized Phrase Structure Grammar. London: Blackwell.

[7]

{Johnson 86} Johnson, M. (1986). Computing with Regular Path Formulas. Ms. CSLI, Stanford, California.

[8]

{Kaplan/Bresnan 82} Kaplan, R. und J. Bresnan (1982). Lexical Functional Grammar: A Formal System for Grammatical Representation. In: J. Bresnan (ed.), The Mental Representation of Grammatical Relations. MIT Press, Cambridge, Massachusetts.

[9]

{Karttunen 84} Karttunen, L. (1984). Features and Values. In: Proceedings of COLING 1984, Stanford, CA.

Digital Library

[10]

{Kasper 87a} Kasper, R.T. (1987). Feature Structures: A Logical Theory with Application to Language Analysis. Ph.D. Thesis. University of Michigan.

Digital Library

[11]

{Kasper 87b} Kasper, R.T. (1987). A Unification Method for Disjunctive Feature Descriptions. In: Proceedings of the 25th Annual Meeting of the ACL. Stanford, CA.

Digital Library

[12]

{Kasper/Rounds 86} Kasper, R. T. and W. Rounds (1986). A Logical Semantics for Feature Structures. In: Proceedings of the 24th Annual Meeting of the ACL. Columbia University, New York, NY.

Digital Library

[13]

{Kay 79} Kay, M. (1979). Functional Grammar. In: C. Chiarello et al. (eds.) Proceedings of the 5th Annual Meeting of the Berkeley Linguistic Society.

[14]

{Kay 85} Kay, M. (1985). Parsing in Functional Unification Grammar. In: D. Dowty, L. Karttunen, and A. Zwicky (eds.) Natural Language Parsing, Cambridge, England.

[15]

{Smolka/Aït-Kaci 87} Smolka, G. and H. Aït-Kaci (1987). Inheritance Hierarchies: Semantics and Unification. MCC Tech. Rep. No AI-057-87. To appear in: Journal of Symbolic Logic, Special Issue on Unification, 1988.

Digital Library

[16]

{Uszkoreit 86} Uszkoreit, H. (1986). Categorial Unification Grammars. In: Proceedings of COLING 1986, Bonn.

Digital Library

Cited By

Lavie ARosé C(2004)Optimal ambiguity packing in context-free parsers with interleaved unificationNew developments in parsing technology10.5555/1139041.1139057(307-321)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.5555/1139041.1139057
Flickinger D(2000)On building a more efficient grammar by exploiting typesNatural Language Engineering10.1017/S13513249000023706:1(15-28)Online publication date: 1-Mar-2000
https://dl.acm.org/doi/10.1017/S1351324900002370
Nakano MShimazu ABoitet CWhitelock P(1998)Translating a unification grammar with disjunctions into logical constraintsProceedings of the 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics - Volume 210.3115/980691.980723(934-938)Online publication date: 10-Aug-1998
https://dl.acm.org/doi/10.3115/980691.980723
Show More Cited By

Recommendations

Feature logic with disjunctive unification
COLING '90: Proceedings of the 13th conference on Computational linguistics - Volume 2

We introduce feature terms containing sorts, variables, negation and named disjunction for the specification of feature structures. We show that the possibility to label disjunctions with names has major advantages both for the use of feature logic in ...
A unification method for disjunctive feature descriptions
ACL '87: Proceedings of the 25th annual meeting on Association for Computational Linguistics

Although disjunction has been used in several unification-based grammar formalisms, existing methods of unification have been unsatisfactory for descriptions containing large quantities of disjunction, because they require exponential time. This paper ...
Semantics for disjunctive logic programs

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

ACL '88: Proceedings of the 26th annual meeting on Association for Computational Linguistics

June 1988

304 pages

Program Chair:
Jerry Hobbs
SRI International

Publisher

Association for Computational Linguistics

United States

Publication History

Published: 07 June 1988

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 85 of 443 submissions, 19%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
220
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)6

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lavie ARosé C(2004)Optimal ambiguity packing in context-free parsers with interleaved unificationNew developments in parsing technology10.5555/1139041.1139057(307-321)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.5555/1139041.1139057
Flickinger D(2000)On building a more efficient grammar by exploiting typesNatural Language Engineering10.1017/S13513249000023706:1(15-28)Online publication date: 1-Mar-2000
https://dl.acm.org/doi/10.1017/S1351324900002370
Nakano MShimazu ABoitet CWhitelock P(1998)Translating a unification grammar with disjunctions into logical constraintsProceedings of the 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics - Volume 210.3115/980691.980723(934-938)Online publication date: 10-Aug-1998
https://dl.acm.org/doi/10.3115/980691.980723
Nederhof M(1996)Efficient generation of random sentencesNatural Language Engineering10.1017/S13513249960012342:1(1-13)Online publication date: 1-Mar-1996
https://dl.acm.org/doi/10.1017/S1351324996001234
Johnson M(1994)Computing with features as formulaeComputational Linguistics10.5555/972509.97251020:1(1-25)Online publication date: 1-Mar-1994
https://dl.acm.org/doi/10.5555/972509.972510
Pereira F(1993)Review of "The logic of typed feature structures" by Bob Carpenter. Cambridge University Press 1992.Computational Linguistics10.5555/972487.97249519:3(544-552)Online publication date: 1-Sep-1993
https://dl.acm.org/doi/10.5555/972487.972495
Strömbäck LZampolli A(1992)Unifying disjunctive feature structuresProceedings of the 14th conference on Computational linguistics - Volume 410.3115/992424.992456(1167-1171)Online publication date: 23-Aug-1992
https://dl.acm.org/doi/10.3115/992424.992456
Nagata MZampolli A(1992)An empirical study on rule granularity and unification interleaving toward an efficient unification-based parsing systemProceedings of the 14th conference on Computational linguistics - Volume 110.3115/992066.992096(177-183)Online publication date: 23-Aug-1992
https://dl.acm.org/doi/10.3115/992066.992096
Damas LVarile GZampolli A(1992)On the satisfiability of complex constraintsProceedings of the 14th conference on Computational linguistics - Volume 110.3115/992066.992086(108-112)Online publication date: 23-Aug-1992
https://dl.acm.org/doi/10.3115/992066.992086
Brew C(1991)Systemic classification and its efficiencyComputational Linguistics10.5555/176321.17632317:4(375-408)Online publication date: 1-Dec-1991
https://dl.acm.org/doi/10.5555/176321.176323
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents