Parsing with StructurePreserving
This book is a study of the logical and computational properties of structurepreserving categorial grammars.
The first part of the book presents chartparsers for nonassociative categorial grammars in the style of Ajdukiewicz and BarHillel. These are proposed in Chapter 3 as deductive parsers, that is as deductive systems which take advantage of the linear order of the syntactic categories. In Chapter 4 they are formulated as polynomial parsing algorithms. An important aspect is the formulation of efficient methods for handling product formulas in the parsing process.
The second part of the book deals with Lambek style categorial grammars. A simple and elegant method for automatic recognition is formulated in Chapter 5 and its syntactic and semantic properties are explored in the subsequent chapters. A surprising result is the connection between the number of semantic readings of a sequent and the binomial coefficient discussed in Chapter 6. The results of polynomiality in Chapter 7 are grounded on explicit algorithms which generalize and improve previous results.
The parsing techniques presented in this book are among the first complete applications of chartparsing methods to logical grammars and lay the ground for a new approach to parsing with typelogical grammars