This paper proposes a method for packing feature structures, which automatically collapses equivalent parts of lexical/phrasal feature structures of HPSG into a single packed feature structure. This method avoids redundant repetition of unification of those parts. Preliminary experiments show that this method can significantly improve a unification speed in parsing.
In order to realize their full potential, multimodal systems need to support not just input from multiple modes, but also synchronized integration of modes. Johnston et al (1997) model this integration using a unification operation over typed feature structures. This is an effective solution for a broad class of systems, but limits multimodal utterances to combinations of a single spoken phrase with a single gesture. We show how the unification-based approach can be scaled up to provide a full multimodal grammar formalism.
This paper proposes a method for generating a logicalconstraint-based internal representation from a unification grammar formalism with disjunctive information. Unification grammar formalisms based on path equations and lists of pairs of labels and values are better than those based on first-order terms in that the former is easier to describe and to understand. Parsing with term-based internal representations is more efficient than parsing with graph-based representations.
This paper introduces a new approach to morpho-syntactic analysis through Humor 99 (High-speed Unification Mo.rphology), a reversible and unification-based morphological analyzer which has already been integrated with a variety o f industrial applications. Humor 99 successfully copes with problems o f agglutinative (e.g. Hungarian, Turkish, Estonian) and other (highly) inflectional languages (e.g. Polish, Czech, German) very effectively.
Log-linear models provide a statistically sound framework for Stochastic "Unification-Based" Grammars (SUBGs) and stochastic versions of other kinds of grammars. We describe two computationally-tractable ways of estimating the parameters of such grammars from a training corpus of syntactic analyses, and apply these to estimate a stochastic version of LexicalFunctional Grammar.
A language processor is to find out a most promising
sentence hypothesis for a given word lattice obtained
from acoustic signal recognition. In this paper a new language processor is proposed, in which unification granunar and Markov language model are integrated in a word lattice parsing algorithm based on an augmented chart, and the island-driven parsing concept is combined with various preference-first parsing strategies defined by different construction principles and decision rules.
This paper describes a structure-sharing method for the representation of complex phrase types in a parser for PATR-[I, a unification-based g r a m m a r formalism. In parsers for unification-based grammar formalisms, complex phrase types are derived by incremental refinement of rite phrase types defined in grammar rules and lexical entries. In a naive implementation, a new phrase type is built by copying older ones and then combining the copies according to the constraints stated in a grammar rule. ...
A grammatical description often applies to a linguistic object only when that object has certain features. Such conditional descriptions can be indirectly modeled in Kay's Functional Unification Grammar (FUG) using functional descriptions that are embedded within disjunctive alternatives. An extension to FUG is proposed that allows for a direct representation of conditional descriptions. This extension has been used to model the input conditions on the systems of systemic grammar. Conditional descriptions are formally defined in terms of logical implication and negation.
Tree Unification Grammar is a declarative unification-bas~:l linguistic framework. The basic grammar stmaures of this framework are partial descriptions of trees, and the framework requires only a single grammar rule to combine these partial descriptions. Using this framework, constraints associated with various linguistic phenomena (reflexivisationin particular)~ be stated succinctlyin the lexicon.
A simple formalism is proposed to represent the contexts in which pronouns, definite/indefinite descriptions, and ordinal descriptions (e.g. 'the second book') can be used, and the way in which these expressions change the context. It is shown that referring expressions can be generated by a unification grammar provided that some phrase-structure rules are specially tailored to express entities in the current knowledge base.
Default inheritance is a useful tool for encoding linguistic generalisations that have exceptions. In this paper we show how the use of an order independent typed default unification operation can provide non-redundant highly structured and concise representation to specify a network of lexical types, that encodes linguistic information about verbal subcategorisation.
Recent empirical research has shown conclusive advantages of multimodal interaction over speech-only interaction for mapbased tasks. This paper describes a multimodal language processing architecture which supports interfaces allowing simultaneous input from speech and gesture recognition. Integration of spoken and gestural input is driven by unification of typed feature structures representing the semantic contributions of the different modes.
The notion of a Horn extended feature structure (HoXF) is introduced, which is a feature structure constrained so that its only allowable extensions are those satisfying some set of llorn clauses in featureterm logic, l l o X F ' s greatly generalize ordinary feature structures in admitting explicit representation of negative and implicational constraints. In contradistinction to the general case in which arbitrary logical constraints are allowed (for which the best known algorithms are exponential), there is a highly tractable algorithm for the unification of HoXF's. ...
A formalism is presented for lexical specification in unification-based grammars which exploits defeasible multiple inheritance to express regularity, subregularity, and exceptions in classifying the properties of words. Such systems are in the general case intractable; the present proposal represents an attempt to reduce complexity while retaining sufficient expressive power for the task at hand. Illustrative examples are given of morphological analyses from English and German.
Graph unification is the most expensive part of unification-based grammar parsing. It often takes over 90% of the total parsing time of a sentence. We focus on two speed-up elements in the design of unification algorithms: 1) elimination of excessive copying by only copying successful unifications, 2) Finding unification failures as soon as possible. We have developed a scheme to attain these two elements without expensive overhead through temporarily modifying graphs during unification to eliminate copying during unification. ...
This paper presents a unification procedure which eliminates the redundant copying of structures by using a lazy incremental copying appr0a~:h to achieve structure sharing. Copying of structures accounts for a considerable amount of the total processing time. Several methods have been proposed to minimize the amount of necessary copying. Lazy Incremental Copying (LIC) is presented as a new solution to the copying problem. It synthesizes ideas of lazy copying with the notion of chronological dereferencing for achieving a high amount of structure sharing. ...
This paper presents a connectionist syntactic parser which uses Structure Unification Grammar as its grammatical framework. The parser is implemented in a connectionist architecture which stores and dynamically manipulates symbolic representations, but which can't represent arbitrary disjunction and has bounded memory. These problems can be overcome with Structure Unification Grammar's extensive use of partial descriptions.
We present an implemented unification-based parser for relational grammars developed within the s t r a t i f i e d f e a t u r e g r a m m a r (SFG) framework, which generalizes Kasper-Rounds logic to handle relational grammar analyses. We first introduce the key aspects of SFG and a lexicalized, graph-based variant of the framework suitable for implementing relational grammars. We then describe a head-driven chart parser for lexicalized SFG.
Motivation for including relational constraints other than equality within grammatical formalisms has come from discontinuous constituency and partially free word order for natural languages as well as from the need to define combinatory operations at the most basic level for languages with a two-dimensional syntax (e.g., mathematical notation, chemical equations, and various diagramming languages). This paper presents F-PATR, a generalization of the PATR-II unification-based formalism, which incorporates relational constraints expressed as user-defined functions. ...
The paper demonstrates that exponential complexities with respect to grammar size and input length have little impact on the performance of three unification-based parsing algorithms, using a wide-coverage grammar. The results imply that the study and optimisation of unification-based parsing must rely on empirical data until complexity theory can more accurately predict the practical behaviour of such parserQ. 1.