Attribute-Value Logic and the Theory of Grammar

Because of the ease of their implementations, attribute-value based theories of grammar are becoming increasingly popular in theoretical linguistics as an alternative to transformational accounts, as well as in computational linguistics. Mark Johnson provides a formal analysis of attribute-value structures, of their use in a theory of grammar, of the representation of grammatical relations in such theories of grammar, and the implications of different representations. A classical treatment of disjunction and negation is also included.

“Essential reading for anyone interested in recent unification-based approaches to grammar. Johnson lucidly lays out a formal framework in which a sharp distinction is drawn between descriptions of linguistic objects and the objects themselves. Negation and disjunction over complex features, though linguistically desirable, have given rise to many problems, and one of Johnson's main achievements is to show that they can be interpreted using classic logic.”
–Ewan Klein, University of Edinburgh

Mark Johnson is assistant professor of cognitive and linguistic sciences at Brown University.

Acknowledgements

1 Introduction

1.1 Attribute-Value Grammar and the Theory of Language
1.2 An Example of an Attribute-Value Grammar
1.3 Previous Work on Attribute-Value Grammar

2 Attribute-Value Structures

2.1 Attribute-Value Structure

2.1.1 The Use of Attribute-Value Structures
2.1.2 The Important Properties of Attribute-Value Structures
2.1.3 A Definition of Attribute-Value Structures
2.1.4 Depicting Attribute-Value Structures
2.1.5 Restricting the Class of Attribute-Value Structures

2.2 A Language for Describing Attribute-Value Structures

2.2.1 The Syntax of Attribute-Value Languages
2.2.2 The Semantics of Attribute-Value Languages

2.3 Attribute-Value Logic
2.4 Soundness of AVL
2.5 Decidability and Completeness of AVL

2.5.1 Reduced Forms
2.5.2 Some Theorem Schemata of AVL
2.5.3 A Norm on Terms and Wffs
2.5.4 An Algorithm for Reducing Wffsto Reduced Forms

2.6 Compactness of 𝒜
2.7 Restricting the Class of Attribute-Value Structures

2.7.1 Finite Attribute-Value Structure
2.7.2 Discernible Attribute-Value Structure
2.7.3 Acrylic Attribute-Value Structure

2.8 Wffs of 𝒜 as Descriptions of Attribute-Value Structures
2.9 The Quantifier-Free Theory with Equality

2.9.1 Quantifier-Free First-order Languages with Equality
2.9.2 A Translation from 𝒜 to ℒ
2.9.3 The COmputational Complexity of Satisfiability in 𝒜

2.10 Attribute-Value Structures and Partiality

2.10.1 Satisfaction and the ‘Unification Approach’
2.10.2 Partial Descriptions and Unification
2.10.3 Unifcation and Satisfaction of Atomic Wffs
2.10.4 Unification and Satisfaction of Arbitrary Wffs
2.10.5 A Comparison with the ‘Unifcation Approach’

2.11 Conclusion

3 The Use of Attribute-Value Structure

3.1 Linguistic Structures in Attribute-Value Based Theories

3.1.1 Tree Domains
3.1.2 Constituent Structures
3.1.3 Annotated Constituent Structures

3.2 The ‘Generates’ Relation in Attribute-Value Based Theories
3.3 Decomposing the Parsing Problem
3.4 Arbitrary Constituent Structures and Undecidability

3.4.1 Turing Machines
3.4.2 Encoding a Turing Machine in Attribute-Value Grammar
3.4.3 Implications of the Undecidability Result

3.5 The Off-Line Parsability Constraint

3.5.1 Enumerating OLP Constituent Structures
3.5.2 An Algorithm for Solving the Universal Parsing Problem

3.6 Conclusion

4 The Encoding of Grammatical Relations

4.1 Encoding Grammatical Relations in AV Grammars
4.2 The ‘Direct Encoding’ of Grammatical Relations

4.2.1 Direct Encoding and Subcategorization
4.2.2 Subcategorization via Diacritic Features
4.2.3 Implications of the Undedability Result

4.3 The ‘Hierchical Encoding’ of Grammatical Relations
4.4 Empirical Differences between Encodings
4.5 The Double Infinitive Construction in West Germanic
4.6 The Double Infinitive Construction in Dutch
4.7 Cross-Serial Dependencies in Dutch
4.8 The BKPZ Analysis of Cross Serial Dependencies
4.9 The BKPZ Analysis and the Double Infinitive Construction
4.10 Overgeneration and the BKPZ Analysis
4.11 Double Infintive COnstruction and Off-line Parsability
4.12 A Hierarchical Encoding Analysis of the DIC

5 Conclusion

5.1 Constraint Equations
5.2 Implementation Issues
5.3 Regular Path Equations
5.4 Linguistic Properties of the Double Infinitive Construction
5.5 Parsing as Deduction

Bibliography
Index

11/1/88

ISBN (Paperback): 0937073369 (9780937073360)
ISBN (Cloth — OUT OF PRINT): 0937073377 (9780937073377)
ISBN (Electronic): 1575866927 (9781575866925)
Subject: Linguistics; Grammar; Computational Linguistics

Attribute-Value Logic and the Theory of Grammar

Contents