Cited By
View all- Baumgartner P(2003)First-order logic Davis-Putnam-Logemann-Loveland procedureExploring artificial intelligence in the new millennium10.5555/779343.779354(289-329)Online publication date: 1-Jan-2003
Computing with features as formulae
Pages 1 - 25
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.
References
[1]
Aït-Kaci, Hassan (1984). A lattice theoretic approach to computation based on a calculus of partially ordered type structures. Doctoral dissertation, University of Pennsylvania.
[2]
Aït-Kaci, Hassan, and Podelski, Andreas (1993). "Towards a meaning of LIFE." The Journal of Logic Programming 16(3, 4), 195--234.
[3]
Alshawi, Hiyan (1992). "Categories and rules." In The Core Language Engine, edited by Hiyan Alshawi, 41--60. MIT Press.
[4]
Barton, G. Edward; Berwick, Robert C.; and Ristad, Eric S. (1987). Computational Complexity and Natural Language. MIT Press.
[5]
Blackburn, Patrick (1991). "Modal logic and attribute-value structures." In Modal Logic Colloquium '91, edited by Maarten de Rijke. Dutch Project for Language, Logic and Information, Amsterdam.
[6]
Blackburn, Patrick, and Spaan, Edith (1992). "A modal perspective on the computational complexity of attribute value grammar." Logic Group Preprint Series No. 77, Department of Philosophy, University of Utrecht.
[7]
Blackburn, Patrick; Gardent, Claire; and Meyer-viol, Wilfried (1993). "Talking about trees." In Proceedings, 6th European Meeting of the Association for Computational Linguistics. Utrecht, Holland.
[8]
Bresnan, Joan (1982). The Mental Representation of Grammatical Relations. MIT Press.
[9]
Carpenter, Bob (1991). "Typed feature structures: A generalization of first-order terms." In Logic Programming, Proceedings of the 1991 International Symposium, edited by Vijay Saraswat and Kazunori Ueda, 187--201. MIT Press.
[10]
Carpenter, Bob (1992). The Logic of Typed Feature Structures. Cambridge Tracts in Theoretical Computer Science 32. Cambridge University Press, Cambridge, England.
[11]
Carpenter, Bob, and Pollard, Carl (1991). "Inclusion, disjointness and choice: The logic of linguistic classification." In Proceedings, 29th Annual Meeting of the Association for Computational Linguistics, 9--16. Berkeley, CA.
[12]
Carpenter, Bob; Pollard, Carl; and Franz, Alex (1991). "The specification and implementation of constraint-based unification grammars." In Proceedings, Second International Workshop on Parsing Technologies. Cancun, Mexico.
[13]
Chang, Chin-Liang, and Lee, Richard Char-Tung (1973). Symbolic Logic and Mechanical Theorem Proving. Academic Press.
[14]
Chomsky, Noam (1986). Knowledge of Language, Its Nature, Origins and Use. Praeger.
[15]
Chomsky, Noam (1988). Some Notes on Economy of Derivation and Representation. ms. Massachusetts Institute of Technology.
[16]
Corman, Thomas H.; Leiserson, Charles E.; and Rivest, Ronald L. (1990). Introduction to Algorithms. MIT Press.
[17]
Dawar, Anuj, and Vijay-Shanker, K. (1990). "An interpretation of negation in feature structures." Computational Linguistics 16(1), 11--21.
[18]
Dörre, Jochen (1991). "The language of STUF." In Text Understanding in LILOG: Integrating Computational Linguistics and Artificial Intelligence, edited by Otthein Herzog and Claus-Rainer Rollinger, 39--50. Springer-Verlag.
[19]
Dörre, Jochen, and Eisele, Andreas (1990). "Feature logic with disjunctive unification." In Proceedings, 13th International Conference on Computational Linguistics (COLING-90), 100--105. Helsinki, Finland.
[20]
Dörre, Jochen, and Eisele, Andreas (1991). "A comprehensive unification-based grammar formalism." DYANA Deliverable R3.1B, ESPRIT Basic Research Action BR3175.
[21]
Dörre, Jochen, and Rounds, William C. (1992). "On subsumption and semiunification in feature algebras." Journal of Symbolic Computation 13, 441--461.
[22]
Duffy, David (1991). Principles of Automated Theorem Proving. John Wiley and Sons.
[23]
Eisele, A., and Dörre, J. (1988). "Unification of disjunctive feature descriptions." In Proceedings, 26th Annual Meeting of the Association for Computational Linguistics, 286--294. Buffalo, New York.
[24]
Emele, Martin (1991). "Unification with lazy non-redundant copying." In Proceedings, 29th Annual Meeting of the Association for Computational Linguistics, 323--330. Berkeley, CA.
[25]
Callier, J. H. (1986). Logic for Computer Science. Harper and Row.
[26]
Genesereth, M., and Nilsson, N. (1987). Logical Foundations of Artificial Intelligence. Morgan Kaufmann.
[27]
Hegner, Stephen J. (1991). "Horn extended feature structures: Fast unification with negation and limited disjunction." In Proceedings, Fifth Conference of the European Chapter of the Association for Computational Linguistics, 33--38. Berlin.
[28]
Höhfeld, Markus, and Smolka, Gert. (1988). "Definite relations over constraint languages." LILOG Report No. 53, IBM Deutschland.
[29]
Johnson, Mark (1988). Attribute-Value Logic and the Theory of Grammar. CSLI Lecture Notes Series. University of Chicago Press.
[30]
Johnson, Mark (1990a). "Expressing disjunctive and negative feature constraints with classical first-order logic." In Proceedings, 28th Annual Meeting of the Association for Computational Linguistics, 173--179. Pittsburgh, PA.
[31]
Johnson, Mark (1990b). "Features, frames and quantifier-free formulae." In Logic and Logic Grammars for Language Processing, edited by Patrick Saint-Dizier and Stan Szpakowicz, 94--107. Ellis Horwood.
[32]
Johnson, Mark (1991a). "Features and formulae." Computational Linguistics 17(2), 131--152.
[33]
Johnson, Mark (1991b). "Logic and feature structures." In Proceedings, International Joint Conference on Artificial Intelligence. Sydney.
[34]
Johnson, Mark (in press a) "Attribute-value logic and natural language processing." In Unification in Grammar, edited by Jürgen Wedekind and Christian Rohrer. MIT Press.
[35]
Johnson, Mark (in press b) "Two ways of formalizing grammars." Linguistics and Philosophy.
[36]
Johnson, Mark, and Kay, Martin (1990). "Semantic operators and anaphora." In Proceedings, 13th International Conference on Computational Linguistics (COLING-90), 17--27. Helsinki.
[37]
Johnson, Mark, and Klein, Ewan (1986). "Discourse, parsing and anaphora." In Proceedings, 11th International Conference on Computational Linguistics. Bonn.
[38]
Kamp, Hans (1981). "A theory of truth and semantic representation." In Formal Methods in the Study of Language, edited by J. A. G. Groenendijk, T. M. V. Janssern, and M. B. J. Stokhof, 277--322. Mathematical Centre Tracts, Amsterdam.
[39]
Kaplan, Ronald M., and Bresnan, Joan (1982). "Lexical-functional grammar, a formal system for grammatical representation." In The Mental Representation of Grammatical Relations, edited by Joan Bresnan, 173--281. MIT Press.
[40]
Kaplan, Ronald M., and Maxwell, John T. (1988a). "An algorithm for functional uncertainty." In Proceedings, 12th International Conference on Computational Linguistics, 297--302. Budapest, Hungary.
[41]
Kaplan, Ronald M., and Maxwell, John T. (1988b). "Constituent coordination in lexical-functional grammar." In Proceedings. 12th International Conference on Computational Linguistics, 297--302. Budapest, Hungary.
[42]
Kaplan, Ronald M., and Zaenen, Annie. (1989). "Long-distance dependencies, constituent structure and functional uncertainty." In Alternative Conceptions of Phrase Structure, edited by Mark Baltin and Anthony Krock, 17--42. Chicago University Press.
[43]
Kapur, D., and Musser, D. R. (1987). "Proof by consistency." Artificial Intelligence 31, 125--157.
[44]
Karttunen, Lauri (1984). "Features and values." In Proceedings, International Conference on Computational Linguistics (COLING-1984), 28--33. Stanford University.
[45]
Kasper, Robert T. (1987a). Feature structures: A logical theory with application to language analysis. Doctoral dissertation, University of Michigan.
[46]
Kasper, Robert T. (1987b). "A unification method for disjunctive feature structures." In Proceedings, 25th Annual Meeting of the Association for Computational Linguistics, 235--242. Stanford University.
[47]
Kasper, Robert T. (1988). "Conditional descriptions in functional unification grammar." In Proceedings, 26th Annual Meeting of the Association for Computational Linguistics, 233--240. Buffalo, N.Y.
[48]
Kasper, Robert T., and Rounds, William C. (1986). "A logical semantics for feature structures." In Proceedings, 24th Annual Meeting of the Association for Computational Linguistics, 257--266. Columbia University, New York.
[49]
Kasper, Robert T., and Rounds, William C. (1990). "The logic of unification in grammar." Linguistics and Philosophy 13(1), 35--58.
[50]
Kay, Martin (1979). "Functional unification grammar." In Proceedings, Fifth Annual Meeting of the Berkeley Linguistics Association. Berkeley, CA.
[51]
Kay, Martin (1985a). "Parsing in functional unification grammar." In Natural Language Parsing, edited by D. R. Dowty, L. Karttunen, and A. M. Zwicky. Cambridge University Press.
[52]
Kay, Martin (1985b). "Unification in grammar." In Natural Language Understanding and Logic Programming, edited by V. Dahl and P. Saint-Dizier, 233--240. North Holland.
[53]
Keller, Bill (1991). Feature logics, infinitary descriptions and the logical treatment of grammar. Doctoral dissertation, University of Sussex.
[54]
Kowalski, Robert (1979). Logic for Problem Solving. North Holland.
[55]
Langholm, Tore (1989). "How to say no with feature structures." COSMOS Report No. 13, Department of Mathematics, University of Oslo.
[56]
Lewis, Harry (1980). "Complexity results for classes of quantificational formulae." JCSS 21, 317--353.
[57]
Lewis, Harry, and Papadimitriou, Christos (1981). Elements of the Theory of Computation. Prentice-Hall, NJ.
[58]
Lloyd, John W. (1984). Foundations of Logic Programming. Springer-Verlag.
[59]
Lobo, Jorge; Minker, Jack; and Rajasekar, Arcot (1992). Foundations of Disjunctive Logic Programming. MIT Press.
[60]
Loveland, D. W. (1987). "Near-Horn Prolog." In Logic Programming: Papers for the Fourth International Conference on Logic Programming, edited by Jean-Louis Lassez, 456--469. MIT Press.
[61]
Marcus, Mitch; Hindle, Donald; and Fleck, Margaret M. (1983). "D-theory---talking about talking about trees." In Proceedings, 21st Annual Meeting of the Association for Computational Linguistics, 129--136. Cambridge, MA.
[62]
Maxwell, John T., and Kaplan, Ronald M. (1991). "A method for disjunctive constraint satisfaction." In Current Issues in Parsing Technology, edited by Masaru Tomita, 173--190. Kluwer Academic Publishers.
[63]
Maxwell, John T., and Kaplan, Ronald M. (1992). "The interface between phrasal and functional constraints." Computational Linguistics 19(4), 571--590.
[64]
Moshier, M. Drew (1988). Extensions to unification grammar for the description of programming languages. Doctoral dissertation, University of Michigan.
[65]
Moshier, M. Drew, and Rounds, William C. (1987). "A logic for partially specified data structures." In The ACM Symposium on the Principles of Programming Languages. Association for Computing Machinery, Munich, Germany.
[66]
Nelson, G., and Oppen, D. C. (1980). "Fast decision procedures based on congruence closure." J. ACM 27(2), 245--257.
[67]
Partee, Barbara H.; ter Meulen, Alice; and Wall, Robert E. (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers.
[68]
Pereira, Fernando C. N. (1982). Logic for natural language analysis. Doctoral dissertation, University of Edinburgh.
[69]
Pereira, Fernando C. N. (1987). "Grammars and logics of partial information." In Proceedings, International Conference on Logic Programming, 989--1013. Melbourne, Australia.
[70]
Pollard, Carl, and Sag, Ivan A. (1987). Information-Based Syntax and Semantics. CSLI Lecture Notes Series. Chicago University Press.
[71]
Pollard, Carl, and Sag, Ivan A. (1992). Head-Driven Phrase Structure Grammar. CSLI Lecture Notes Series. Chicago University Press.
[72]
Rounds, William C. (1988). "LFP: A logic for linguistic descriptions and an analysis of its complexity." Computational Linguistics 14(4), 1--9.
[73]
Rounds, William C., and Manaster-Ramer, Alexis (1987). "A logical version of functional grammar." In Proceedings, 25th Annual Meeting of the Association for Computational Linguistics, 89--96. Stanford, CA.
[74]
Shieber, Stuart M. (1986). An Introduction to Unification-Based Approaches to Grammar. CSLI Lecture Notes Series. University of Chicago Press.
[75]
Shieber, Stuart M. (1992). Constraint-Based Grammar Formalisms: Parising and Type Inference for Natural and Computer Languages. MIT Press.
[76]
Smolka, Gert. (1988). "A feature logic with suborts." LILOG Report No. 33, IBM Deutschland GmbH.
[77]
Smolka, Gert. (1992). "Feature constraint logics for unification grammars." The Journal of Logic Programming 12(1, 2), 51--87.
[78]
Ullman, Jeffrey D. (1988). Principles of Database and Knowledge-Base Systems, vol. I. Computer Science Press.
[79]
Ullman, Jeffrey D. (1989). Principles of Database and Knowledge-Base Systems, Vol. II: The New Technologies. Computer Science Press.
[80]
Uszkoreit, Hans (1986). "Categorial unification grammar." In Proceedings, 11th International Conference on Computational Linguistics, 187--194. Bonn.
[81]
Vijay-Shanker, K. (1992). "Using descriptions of trees in a tree adjoining grammar." Computational Linguistics 18(4), 481--517.
[82]
Wall, Robert (1972). Introduction to Mathematical Linguistics. Prentice-Hall.
[83]
Zajac, Rémi (1992). "Inheritance and constraint-based grammar formalisms." Computational Linguistics 18(2), 159--182.
- Computing with features as formulae
Recommendations
Loop formulas for circumscription
Clark's completion is a simple nonmonotonic formalism and a special case of several nonmonotonic logics. Recently there has been work on extending completion with ''loop formulas'' so that general cases of nonmonotonic logics such as logic programs (...
Computing Equilibrium Models Using Signed Formulas
CL '00: Proceedings of the First International Conference on Computational LogicWe discuss equilibrium logic, first presented in Pearce (1997), as a system of nonmonotonic reasoning based on the nonclassical logic N5 of here-and-there with strong negation. Equilibrium logic is a conservative extension of answer set inference, not ...
A Reduction Result for Circumscribed Semi-Horn Formulas
Circumscription has been perceived as an elegant mathematical technique for modeling nonmonotonic and commonsense reasoning, but difficult to apply in practice due to the use of second-order formulas. One proposal for dealing with the computational ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
MIT Press
Cambridge, MA, United States
Publication History
Published: 01 March 1994
Published in COLI Volume 20, Issue 1
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 119Total Downloads
- Downloads (Last 12 months)25
- Downloads (Last 6 weeks)3
Reflects downloads up to 16 Nov 2024
Other Metrics
Citations
Cited By
View all- Baumgartner P(2003)First-order logic Davis-Putnam-Logemann-Loveland procedureExploring artificial intelligence in the new millennium10.5555/779343.779354(289-329)Online publication date: 1-Jan-2003
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in