Polynomial time parsing

Xem 1-11 trên 11 kết quả Polynomial time parsing
  • In this paper we present a polynomial time parsing algorithm for Combinatory Categorial Grammar. The recognition phase extends the CKY algorithm for CFG. The process of generating a representation of the parse trees has two phases. Initially, a shared forest is build that encodes the set of all derivation trees for the input string. This shared forest is then pruned to remove all spurious ambiguity.

    pdf8p bungio_1 03-05-2013 25 1   Download

  • This paper investigates the class of TreeTuple MCTAG with Shared Nodes, TTMCTAG for short, an extension of Tree Adjoining Grammars that has been proposed for natural language processing, in particular for dealing with discontinuities and word order variation in languages such as German. It has been shown that the universal recognition problem for this formalism is NP-hard, but so far it was not known whether the class of languages generated by TT-MCTAG is included in PTIME. We provide a positive answer to this question, using a new characterization of TTMCTAG. ...

    pdf9p hongphan_1 14-04-2013 26 2   Download

  • We introduce an algorithm for designing a predictive left to right shift-reduce non-deterministic push-down machine corresponding to an arbitrary unrestricted context-free grammar and an algorithm for efficiently driving this machine in pseudo-parallel. The performance of the resulting parser is formally proven to be superior to Earley's parser (1970). The technique employed consists in constructing before run-time a parsing table that encodes a nondeterministic machine in the which the predictive behavior has been compiled out. ...

    pdf8p bunmoc_1 20-04-2013 37 2   Download

  • We propose an O(M(n2)) time algorithm for the recognition of Tree Adjoining Languages (TALs), where n is the size of the input string and M(k) is the time needed to multiply two k x k boolean matrices. Tree Adjoining Grammars (TAGs) are formalisms suitable for natural language processing and have received enormous attention in the past among not only natural language processing researchers but also algorithms designers. The first polynomial time algorithm for TAL parsing was proposed in 1986 and had a run time of O(n6). has been proposed. ...

    pdf8p bunmoc_1 20-04-2013 34 2   Download

  • The theoretical study of the range concatenation grammar [RCG] formalism has revealed many attractive properties which may be used in NLP. In particular, range concatenation languages [RCL] can be parsed in polynomial time and many classical grammatical formalisms can be translated into equivalent RCGs without increasing their worst-case parsing time complexity. For example, after translation into an equivalent RCG, any tree adjoining grammar can be parsed in time.

    pdf8p bunrieu_1 18-04-2013 37 1   Download

  • Parallel Multiple Context-Free Grammar (PMCFG) is an extension of context-free grammar for which the recognition problem is still solvable in polynomial time. We describe a new parsing algorithm that has the advantage to be incremental and to support PMCFG directly rather than the weaker MCFG formalism. The algorithm is also top-down which allows it to be used for grammar based word prediction.

    pdf8p bunthai_1 06-05-2013 26 1   Download

  • We present a fast, space efficient and nonheuristic method for calculating the decision function of polynomial kernel classifiers for NLP applications. We apply the method to the MaltParser system, resulting in a Java parser that parses over 50 sentences per second on modest hardware without loss of accuracy (a 30 time speedup over existing methods). The method implementation is available as the open-source splitSVM Java library.

    pdf4p hongphan_1 15-04-2013 30 4   Download

  • We develop a general dynamic programming technique for the tabulation of transition-based dependency parsers, and apply it to obtain novel, polynomial-time algorithms for parsing with the arc-standard and arc-eager models. We also show how to reverse our technique to obtain new transition-based dependency parsers from existing tabular methods. Additionally, we provide a detailed discussion of the conditions under which the feature models commonly used in transition-based parsing can be integrated into our algorithms. ...

    pdf10p hongdo_1 12-04-2013 49 5   Download

  • We present a syntax-based statistical translation model. Our model transforms a source-language parse tree into a target-language string by applying stochastic operations at each node. These operations capture linguistic differences such as word order and case marking. Model parameters are estimated in polynomial time using an EM algorithm. The model produces word alignments that are better than those produced by IBM Model 5. is conditioned only on word classes and positions in the string, and the duplication and translation are conditioned only on the word identity. ...

    pdf8p bunrieu_1 18-04-2013 46 4   Download

  • An important goal of computational linguistics has been to use linguistic theory to guide the construction of computationally efficient real-world natural language processing systems. At first glance, generalized phrase structure grammar (GPSG) appears to be a blessing on two counts. First, the precise formalisms of GPSG might be a direct and fransparent guide for parser design and implementation. Second, since GPSG has weak context-free generative power and context-free languages can be parsed in O(n ~) by a wide range of algorithms, GPSG parsers would appear to run in polynomial time.

    pdf10p bungio_1 03-05-2013 27 1   Download

  • The notion of mild context-sensitivity was formulated in an attempt to express the formal power which is both necessary and sufficient to define the syntax of natural languages. However, some linguistic phenomena such as Chinese numbers and German word scrambling lie beyond the realm of mildly contextsensitive formalisms. On the other hand, the class of range concatenation grammars provides added power w.r.t, mildly context-sensitive grammars while keeping a polynomial parse time behavior.

    pdf8p bunthai_1 06-05-2013 33 2   Download



p_strKeyword=Polynomial time parsing

nocache searchPhinxDoc


Đồng bộ tài khoản