Feature Logics, Infinitary Descriptions, and Grammar

Constraint and unification-based approaches to grammar have become increasingly popular in computational linguistics because of their flexibility and descriptive power. These approaches have developed an important notion of feature structures that play a key role in the representation of linguistic information. This book provides a detailed survey and comparison of recent approached tot he logical formalization of feature structures and their description languages in constraint and unification-based grammar formalisms.

Bill Keller is a lecturer in computer science and artificial intelligence in the School of Cognitive and Computing Sciences a the University of Sussex.

Preface

1 Introduction

1.1 Outline of this Book
1.2 Constraint-Based Grammar Formalisms
1.3 Feature Structures
1.4 Formal Models of Feature Structures

2 A Survey of Feature Logics

2.1 A Denotational Model of Descriptions

2.1.1 Feature Structures and Descriptions
2.1.2 The Problem of Negation and Disjunction
2.1.3 Summary

2.2 Rounds-Kasper Logic

2.2.1 The Domains of Feature Structures
2.2.2 The Language of Rounds-Kasper Logic
2.2.3 Partial Information and Treatment of Negation
2.2.4 Typed Feature Structures and Inheritance
2.2.5 Constraint Systems and Grammars

2.3 Category Logic
2.4 Attribute-Value Logic
2.5 Smolka's Features Logic

2.5.1 Feature Algebras
2.5.2 Syntax and Semantics of Feature Terms
2.5.3 Sort Definitions

2.6 Summary

3 Regular Rounds-Kasper Logic

3.1 Unbounded Dependencies
3.2 LFG and Functional Uncertainty
3.3 Regular Rounds-Kasper Logic

3.3.1 The Language of Regular Rounds-Kasper Logic
3.3.2 Logical Equivalences for Descriptions

3.4 The Satisfiability Problem

3.4.1 The Kaplan-Maxwell Algorithm
3.4.2 RRK and Free Descriptions
3.4.3 An Indirect Approach to the Satisfiability Problem

3.5 Conclusion

4 Regular Rounds-Kasper Logic with Negation

4.1 Syntax and Semantics
4.2 Expressing Generalizations in NRRK
4.3 NRRKand Category Logic

4.3.1 A Translation From L_C to NRRK

4.4 NRRK and the Satisfiability Problem

4.4.1 Encoding a Turing Machine in NRRK

4.5 Conclusions

5 Infinitary Descriptions and Grammars

5.1 Constituent Structure

5.1.1 A Representation for Constituent-Structure Trees
5.1.2 Describing Consituent Structure

5.2 Representing Grammars in NRRK

5.2.1 Simple Context-Free Grammar
5.2.2 ID/LP Grammar
5.2.3 PATR
5.2.4 Categorical Grammar
5.2.5 Tree Ajoining Grammar

5.3 Discussion

6 Conclusion

6.1 Closing Remarks

Bibliography

9/1/93

ISBN (Paperback): 1881526259 (9781881526254)
ISBN (Cloth): 1881526267 (9781881526261)

Feature Logics, Infinitary Descriptions, and Grammar

Contents