Articles

In this paper we describe an approach to constraint based syntactic theories in terms of finite tree automata. The solutions to constraints expressed in weak monadic sec- ond order (MSO) logic are represented by tree automata recognizing the assignments which make the formulas true. We show that this allows an …...

We describe a method for interpreting ab- stract fiat syntactic representations, LFG f- structures, as underspecified semantic rep- resentations, here Underspecified Discourse Representation Structures (UDRSs). The method establishes a one-to-one correspon- dence between subsets of the LFG and UDRS formalisms. It provides a model theoretic interpretation and an inferen- tial …...

We describe a simple variant of the inter- polated Markov model with non-emitting state transitions and prove that it is strictly more powerful than any Markov model. Empirical results demonstrate that the non-emitting model outperforms the inter- polated model on the Brown corpus and on the Wall Street Journal under …...

This paper introduces new methods based on exponential families for modeling the correlations between words in text and speech. While previous work assumed the effects of word co-occurrence statistics to be constant over a window of several hun- dred words, we show that their influence is nonstationary on a much …...

Decoding algorithm is a crucial part in sta- tistical machine translation. We describe a stack decoding algorithm in this paper. We present the hypothesis scoring method and the heuristics used in our algorithm. We report several techniques deployed to improve the performance of the decoder. We also introduce a simplified …...

We compare the effectiveness of two related • machine translation models applied to the same limited-domain task. One is a trans- fer model with monolingual head automata for analysis and generation; the other is a direct transduction model based on bilin- gual head transducers. We conclude that the head transducer …...

This paper describes an approach to ex- tract the aspectual information of Japanese verb phrases from a monolingual corpus. We classify Verbs into six categories by means of the aspectual features which are defined on the basis of the possibility of co-occurrence with aspectual forms and ad- verbs. A unique …...

Recent work has seen the emergence of a common framework for parsing categorial grammar (CG) formalisms that fall within the 'type-logical' tradition (such as the Lambek calculus and related systems), whereby some method of linear logic the- orem proving is used in combination with a system of labelling that ensures …...

Results of computational complexity exist for a wide range of phrase structure-based gram- mar formalisms, while there is an apparent lack of such results for dependency-based for- malisms. We here adapt a result on the com- plexity of ID/LP-grammars to the dependency framework. Contrary to previous studies on heavily restricted …...

This paper presents a trainable rule-based algorithm for performing word segmen- tation. The algorithm provides a sim- ple, language-independent alternative to large-scale lexicai-based segmenters requir- ing large amounts of knowledge engineer- ing. As a stand-alone segmenter, we show our algorithm to produce high performance Chinese segmentation. In addition, we show …...

We propose a unified framework in which to treat semantic underspecification and parallelism phenomena in discourse. The framework employs a constraint language that can express equality and subtree rela- tions between finite trees. In addition, our constraint language can express the equal- ity up-to relation over trees which cap- tures …...

The first step in most empirical work in multilingual NLP is to construct maps of the correspondence between texts and their translations (bitext maps). The Smooth Injective Map Recognizer (SIMR) algo- rithm presented here is a generic pattern recognition algorithm that is particularly well-suited to mapping bitext correspon- dence. SIMR …...

This paper presents a new approach to bitext correspondence problem (BCP) of noisy bilingual corpora based on image processing (IP) techniques. By using one of several ways of estimating the lexical translation probability (LTP) between pairs of source and target words, we can turn a bitext into a discrete gray-level …...

Recent empirical research has shown con- clusive advantages of multimodal interac- tion over speech-only interaction for map- based tasks. This paper describes a mul- timodal language processing architecture which supports interfaces allowing simulta- neous input from speech and gesture recog- nition. Integration of spoken and gestural input is driven by …...

This paper presents PARADISE (PARAdigm for Dialogue System Evaluation), a general framework for evaluating spoken dialogue agents. The framework decouples task require- ments from an agent's dialogue behaviors, sup- ports comparisons among dialogue strategies, enables the calculation of performance over subdialogues and whole dialogues, specifies the relative contribution of various …...

To understand a speaker's turn of a con- versation, one needs to segment it into in- tonational phrases, clean up any speech re- pairs that might have occurred, and iden- tify discourse markers. In this paper, we argue that these problems must be resolved together, and that they must be …...

This paper presents an algorithm for the compilation of regular formalisms with rule features into finite-state automata. Rule features are incorporated into the right context of rules. This general notion can also be applied to other algorithms which compile regular rewrite rules into au- tomata. 1...

In this paper, we argue for the need to dis- tinguish between task and dialogue initiatives, and present a model for tracking shifts in both types of initiatives in dialogue interactions. Our model predicts the initiative holders in the next dialogue turn based on the current initia- tive holders and …...

Concerning different approaches to auto- matic PoS tagging: EngCG-2, a constraint- based morphological tagger, is compared in a double-blind test with a state-of-the-art statistical tagger on a common disambigua- tion task using a common tag set. The ex- periments show that for the same amount of remaining ambiguity, the error …...

This paper proposes a mistake-driven mix- ture method for learning a tag model. The method iteratively performs two proce- dures: 1. constructing a tag model based on the current data distribution and 2. updating the distribution by focusing on data that are not well predicted by the constructed model. The …...