Algorithms for polynomials

We develop a general dynamic programming technique for the tabulation of transitionbased dependency parsers, and apply it to obtain novel, polynomialtime algorithms for parsing with the arcstandard and arceager models. We also show how to reverse our technique to obtain new transitionbased dependency parsers from existing tabular methods. Additionally, we provide a detailed discussion of the conditions under which the feature models commonly used in transitionbased parsing can be integrated into our algorithms. ...
10p hongdo_1 12042013 25 5 Download

Note immediately one diﬀerence between linear equations and polynomial equations: theorems for linear equations don’t depend on which ﬁeld k you are working over, 1 but those for polynomial equations depend on whether or not k is algebraically closed and (to a lesser extent) whether k has characteristic zero. Since I intend to emphasize the geometry in this course, we will work over algebraically closed ﬁelds for the major part of the course.
157p tiramisu0908 30102012 19 3 Download

The lexicalist approach to Machine Translation offers significant advantages in the development of linguistic descriptions. However, the ShakeandBake generation algorithm of (Whitelock, 1992) is NPcomplete. We present a polynomial time algorithm for lexicalist MT generation provided that sufficient information can be transferred to ensure more determinism.
7p bunmoc_1 20042013 15 1 Download

We introduce a polynomialtime algorithm for statistical machine translation. This algorithm can be used in place of the expensive, slow bestfirst search strategies in current statistical translation architectures. The approach employs the stochastic bracketing transduction grammar (SBTG) model we recently introduced to replace earlier word alignment channel models, while retaining a bigram language model. The new algorithm in our experience yields major speed improvement with no significant loss of accuracy. ...
7p bunmoc_1 20042013 14 1 Download

Many problems of practical significance are NPcomplete but are too important to abandon merely because obtaining an optimal solution is intractable (khó). If a problem is NPcomplete, we are unlikely to find a polynomial time algorithm for solving it exactly, but it may still be possible to find nearoptimal solution in polynomial time.
22p lucky156 04062010 125 18 Download

Tuyển tập các báo cáo nghiên cứu về sinh học được đăng trên tạp chí sinh học Journal of Biology đề tài: Research Article PolynomialTime Algorithm for Controllability Test of a Class of Boolean Biological Networks
13p dauphong15 16022012 31 4 Download

Tuyển tập các báo cáo nghiên cứu về sinh học được đăng trên tạp chí y học Molecular Biology cung cấp cho các bạn kiến thức về ngành sinh học đề tài: A polynomial time biclustering algorithm for finding approximate expression patterns in gene expression time series...
39p hoami_2511 21102011 25 2 Download

Tuyển tập các báo cáo nghiên cứu về sinh học được đăng trên tạp chí y học Molecular Biology cung cấp cho các bạn kiến thức về ngành sinh học đề tài: Polynomial algorithms for the Maximal Pairing Problem: efficient phylogenetic targeting on arbitrary trees...
10p hoami_2511 21102011 20 2 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 NPhard, but so far it was not known whether the class of languages generated by TTMCTAG is included in PTIME. We provide a positive answer to this question, using a new characterization of TTMCTAG. ...
9p hongphan_1 14042013 15 2 Download

We introduce an algorithm for designing a predictive left to right shiftreduce nondeterministic pushdown machine corresponding to an arbitrary unrestricted contextfree grammar and an algorithm for efficiently driving this machine in pseudoparallel. The performance of the resulting parser is formally proven to be superior to Earley's parser (1970). The technique employed consists in constructing before runtime a parsing table that encodes a nondeterministic machine in the which the predictive behavior has been compiled out. ...
8p bunmoc_1 20042013 23 2 Download

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.
8p bungio_1 03052013 15 1 Download

In this paper we consider a combinatorial optimization problem that is similar to the bottleneck traveling salesman problem. We show that an optimal tour for this problem is pyramidal tour (1, 3, 5,…, n,…, 6, 4, 2) or consists of some pyramidal subtours. The above 7methods can be extended to complete bipartite graphs. 1. Problem statement It is wellknown that the traveling salesman problem (TSP) is strongly NPhard (cf. [1], p. 353). But for some special cases of the TSP can be solvable in polynomial time. ...
5p tuanlocmuido 19122012 24 3 Download

In this book you find the basic mathematics that is needed by engineers and university students . The author will help you to understand the meaning and function of mathematical concepts. The best way to learn it, is by doing it, the exercises in this book will help you do just that.
122p tuanloc_do 03122012 14 1 Download

This topic reviews the basic mathematics required in this course: A justification for a mathematical framework, the ceiling and floor functions, L’Hôpital’s rule, logarithms, arithmetic and other polynomial series, geometric series, recurrence relations, weighted averages, combinations.
50p allbymyself_08 22022016 8 1 Download

In this topic, we will look at: Justification for analysis, quadratic and polynomial growth, counting machine instructions, Landau symbols, BigQ as an equivalence relation, littleo as a weak ordering.
55p allbymyself_08 22022016 5 1 Download

We present a polynomialtime algorithm that provably recovers the signer’s secret DSA key when a few bits of the random nonces k (used at eachsignature generation) are known for a number of DSA signatures at most linear inlog q (q denoting as usual the small prime of DSA), under a reasonable assumption on the hash function used in DSA.
26p dunglh2013 02042014 16 0 Download

We discuss the use of social networks in implementing viral marketing strategies. While influence maximization has been studied in this context (see Chapter 24 of [10]), we study revenue maximization, arguably, a more natural objective. In our model, a buyer’s decision to buy an item is influenced by the set of other buyers that own the item and the price at which the item is offered. We focus on algorithmic question of finding revenue maximizing marketing strategies. When the buyers are completely symmetric, we can find the optimal marketing strategy in polynomial time.
10p doiroimavanchuadc 06022013 24 5 Download

We augment a model of translation based on reordering nodes in syntactic trees in order to allow alignments not conforming to the original tree structure, while keeping computational complexity polynomial in the sentence length. This is done by adding a new subtree cloning operation to either treetostring or treetotree alignment algorithms.
8p bunbo_1 17042013 17 3 Download

We present a new chart parsing method for Lambek grammars, inspired by a method for DTree grammar parsing. The formulae of a Lambek sequent are firstly converted into rules of an indexed grammar formalism, which are used in an Earleystyle predictive chart algorithm. The method is nonpolynomial, but performs well for practical purposes   much better than previous chart methods for Lambek grammars.
8p bunrieu_1 18042013 16 3 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. ...
8p bunmoc_1 20042013 21 2 Download