This paper presents a template-based English-Chinese translation system characterized by two important features: Fast Optimal parsing Algorithm (FOPA) and Universal Algorithm of Matching and Replacing Templates (UAAMT...
详细信息
ISBN:
(纸本)9780769529301
This paper presents a template-based English-Chinese translation system characterized by two important features: Fast Optimal parsing Algorithm (FOPA) and Universal Algorithm of Matching and Replacing Templates (UAAMT). First, the FOPA parses an English sentence into an optimal parse tree or template structure quickly. Second, the UAMRT matches each source template with the optimal structure and replaces it with the corresponding target template. The basic idea of the template-based system is to represent all translation knowledge in uniform templates which can be shown as context-free grammar rules. It then translates an English sentence into Chinese with FOPA and UAMRT System evaluation shows encouraging and promising results for quality and speed, and the system may perform better by adding more templates without any other changes.
We present new results on the relation between purely symbolic context-free parsing strategies and their probabilistic counterparts. Such parsing strategies are seen as constructions of push-down devices from grammars...
详细信息
We present new results on the relation between purely symbolic context-free parsing strategies and their probabilistic counterparts. Such parsing strategies are seen as constructions of push-down devices from grammars. We show that preservation of probability distribution is possible under two conditions, viz. the correct-prefix property and the property of strong predictiveness. These results generalize existing results in the literature that were obtained by considering parsing strategies in isolation. From our general results, we also derive negative results on so-called generalized LR parsing.
We prove that, given as input two context-free grammars, deciding non-emptiness of intersection of the two generated languages is PSPACE-complete if at least one grammar is non-recursive. The problem remains PSPACE-co...
详细信息
We prove that, given as input two context-free grammars, deciding non-emptiness of intersection of the two generated languages is PSPACE-complete if at least one grammar is non-recursive. The problem remains PSPACE-complete when both grammars are non-recursive and deterministic. Also investigated are generalizations of the problem to several context-free grammars, of which a certain number are non-recursive. (C) 2004 Elsevier Inc. All rights reserved.
We present a novel generative model for natural language tree structures in which semantic (lexical dependency) and syntactic (PCFG) structures are scored with separate models. This factorization provides conceptual s...
详细信息
ISBN:
(纸本)0262025507
We present a novel generative model for natural language tree structures in which semantic (lexical dependency) and syntactic (PCFG) structures are scored with separate models. This factorization provides conceptual simplicity, straightforward opportunities for separately improving the component models, and a level of performance comparable to similar, non-factored models. Most importantly, unlike other modern parsing models, the factored model admits an extremely effective A* parsing algorithm, which enables efficient, exact inference.
In this paper, we are concerned with identifying a subclass of tree adjoining grammars (TAGs) that is suitable for the application to modeling and predicting RNA secondary structures. The goal of this paper is twofold...
详细信息
In this paper, we are concerned with identifying a subclass of tree adjoining grammars (TAGs) that is suitable for the application to modeling and predicting RNA secondary structures. The goal of this paper is twofold: For the purpose of applying to the RNA secondary structure prediction problem, we first introduce a special subclass of TAGs and develop a fast parsing algorithm for the subclass, together with some of its language theoretic characterizations. Then, based on the algorithm, we develop a prediction system and demonstrate the effectiveness of the system by presenting some experimental results obtained from biological data, where free energy evaluation selection for parse trees is incorporated into the algorithm. (C) 1999-Elsevier Science B.V. All rights reserved.
K-depth grammars extend context-free grammars allowing k greater than or equal to 1 rewriting points for a single non-terminal at every step of a derivation. The family of languages generated by k-depth grammars is a ...
详细信息
K-depth grammars extend context-free grammars allowing k greater than or equal to 1 rewriting points for a single non-terminal at every step of a derivation. The family of languages generated by k-depth grammars is a proper extension of the family of context-free languages, while retaining many context-free properties, such as closure properties, a version of Chomsky-Schutzenberger theorem, the existence of an accepting device (the multi-pushdown automaton). Here a polynomial-time parsing algorithm for k-depth languages is defined, and its correctness is proved. (C) 1996 Academic Press, Inc.
Incremental integrated programming environments are a promising approach toward the goal of improved programmer productivity. Consistently rapid environment response is an obvious goal. Efficient use of storage has al...
详细信息
Incremental integrated programming environments are a promising approach toward the goal of improved programmer productivity. Consistently rapid environment response is an obvious goal. Efficient use of storage has also been determined to be an important issue. This paper presents the algorithms and techniques used for incremental scanning and parsing of the Galaxy language. The algorithms guarantee minimal rescanning and reparsing and are also space and time efficient. Notably, the methods are easily adapted to any language of equivalent class, i.e., RL(1) intersects LR(1), including such languages as C and Pascal.
We study regularly controlled bidirectional (RCB) grammars from the viewpoint of time-bounded grammars. RCB-grammars are context-free grammars of which the rules can be used in a productive and in a reductive fashion,...
详细信息
This paper presents a canonical form for context-sensitive derivations and a parsing algorithm which finds each context-sensitive analysis once and only once. The amount of memory required by the algorithm is essentia...
详细信息
This paper presents a canonical form for context-sensitive derivations and a parsing algorithm which finds each context-sensitive analysis once and only once. The amount of memory required by the algorithm is essentially no more than that required to store a single complete derivation. In addition, a modified version of the basic algorithm is presented which blocks infinite analyses for grammars which contain loops. The algorithm is also compared with several previous parsers for context-sensitive grammars and general rewriting systems, and the difference between the two types of analyses is discussed. The algorithm appears to be complementary to an algorithm by S. Kuno in several respects, including the space-time trade-off and the degree of context dependence involved.
暂无评论