(Tex source is included for people who want a quasi-plain text version, or are curious as to how tex works for linguistic stuff. Don't expect the files to compile as is, though -- you'll need some support files that aren't here.)

Papers

GIDLP: A Grammar Format for Linearization-based HPSG.

Co-written with Detmar Meurers. Presented at the Eleventh International Conference on Head-Driven Phrase Structure Grammar (HPSG 04) in Leuven, Belgium on August 4, 2004.

Describes and illustrates the GIDLP formalism.

Published as:

Daniels, Michael W. and W. Detmar Meurers. 2004. GIDLP: A Grammar Format for Linearization-based HPSG. In Proceedings of the HPSG-2004 Conference, Center for Computational Linguistics, Katholieke Universiteit Leuven, edited by Stefan Mueller, 93-111. Stanford: CSLI Publications.

A Grammar Formalism and Parser for Linearization-based HPSG.

Co-written with Detmar Meurers. Presented at the Twentieth International Conference on Computational linguistics (COLING 2004). Geneva, Switzerland, August 23-27, 2004.

Linearization-based HPSG theories are widely used for analyzing languages with relatively free constituent order. This paper introduces the Generalized ID/LP (GIDLP) grammar format, which supports a direct encoding of such theories, and discusses key aspects of a parser that makes use of the dominance, precedence, and linearization domain information explicitly encoded in this grammar format. We show that GIDLP grammars avoid the explosion in the number of rules required under a traditional phrase structure analysis of free constituent order. As a result, GIDLP grammars support more modular and compact grammar encodings and require fewer edges in parsing.

Published as:

Daniels, Michael W. and W. Detmar Meurers. 2004. A Grammar Formalism and Parser for Linearization-based HPSG. In Proceedings of the Twentieth International Conference on Computational Linguistics (COLING 2004), 169-175. Geneva, Switzerland: COLING.

Improving the efficiency of parsing with discontinuous constituents

Co-written with Detmar Meurers.

An updated version of the paper presented at (and available from) NLULP 02 -- the 7th International Workshop on Natural Language Understanding and Logic Programming.

This paper discusses a generalization of Earley's algorithm for parsing context-free grammars to handle grammars licensing discontinuous constituents (for instance, as required by a language with relatively-free word order). We show how bitvectors, traditionally used to represent the coverage of a discontinuous constituent, can also be used to encode constraints over possible constituent orderings. This improves the efficiency of edge access and reduces the number of edges in the chart by constraining prediction to just those grammar rules which are compatible with known word order properties. The resulting parsing algorithm does not have to process the righthand side categories in the order in which they occur in the string, and so the grammar writer can specify the complete order in which the righthand side categories will be recognized. This provides an advantage over a head-driven parser, in which the grammar writer can only specify the righthand side category that will be recognized first.

(Versions below include revised sample parse.)

Slides from NLULP 2002 presentation of this paper:

Slides from a department colloquium on this topic:

My second pre-generals paper is an updated and revised version of this paper:

On a Type-Based Treatment of Feature Indeterminacy and the Coordination of Unlikes

An updated and revised version of Daniels 2002.

Ingria (1990) claims that both feature neutrality (where a sign acts in a sentence as though it simultaneously had multiple values for a single feature) and the coordination of unlike categories (where the features of two or more conjuncts differ from each other) pose fundamental problems for unification-based theories of grammar. These claims do not apply to a constraint-based theory like HPSG. New types can be introduced into the signature that directly represent neutralizations and coordinations. From this, feature neutralization and the coordination of unlikes are seen to be different aspects of the same problem: how to determine the values of a coordinate mother's features from those of its conjuncts.

revised April 26, 2002

Slides from a department colloquium on this paper: