The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
By combining the principles of known factoring algorithms we obtain some improved algorithms which by heuristic arguments all have a time bound O(exp √c ln n ln ln n) for various constants c≥3. In particular, Miller's method of solving index equations and Shanks's method of computing ambiguous quadratic forms with determinant −n can be modified in this way. We show how to speed up the factorization...
Let F be a n-variate polynomial with deg F = d over an infinite field k0. Absolute primality of F can be decided randomly in time polynomial in n and exponential in d5 and determinalistically in time exponential in d6 + n2 d3.
In this paper we present a class of VLSI networks for computing the Discrete Fourier Transform and the product of two N-bit integers. These networks match, within a constant factor, the known theoretical lower-bound O(N2) to the area × (time)2 measure of complexity. While this paper's contribution is mainly theoretical, it points toward very practical directions: we show how to design multipliers...
An embedding of the graph G in the graph H is a one-to-one association of the vertices of G with the vertices of H. There are two natural measures of the cost of a graph embedding, namely, the dilation-cost of the embedding: the maximum distance in H between the images of vertices that are adjacent in G, and the expansion-cost of the embedding: the ratio of the size of H to the size of G. The main...
Let N be a planar undirected network with distinguished vertices s, t, a total of n vertices, and each edge labeled with a positive real (the edge's cost) from a set L. This paper presents an algorithm for computing a minimum (cost) s-t cut of N. For general L, this algorithm runs in time O(n log2(n)) time on a (uniform cost criteria) RAM. For the case L contains only integers ≤n0(1), the algorithm...
In this paper we study the implication and the finite implication problems for data dependencies. When all dependencies are total the problems are equivalent and solvable but are NP-hard, i.e., probably computationally intractable. For non-total dependencies the implication problem is unsolvable, and the finite implication problem is not even partially solvable. Thus, there can be no formal system...
We characterize the class of Full Implicational Dependencies introduced by Fagin as the maximal class of dependencies which are safe, admit finite models in a strong sense and admit Armstrong Relations. We also give other more modeltheoretic characterizations of Full and Embedded Implicational Dependencies.
A precise and efficient data-flow analysis algorithm, for analysis of programs involving procedures with call-by-value parameter passing, is presented and analyzed. It is adapted to handle analysis of applicative programs written in a subset of LISP, but is equally suited to analyze programs written in many other languages, such as ADA, APL and SETL.
A new method for the specification of abstract data types is presented. Being algorithmic it avoids several difficulties of the algebraic specification method.
A nondeterministic operation is characterized by the fact that its application to a given set of parameters can yield any one of several possible outcomes. This paper discusses ways to specify, implement, and reason about nondeterministic operations in the context of abstract (algebraic) data types. The notion of an implementation of a data type that includes nondeterministic operations is formalized,...
We shall briefly survey what the author believes are some of the most fruitful directions in relational database theory. These directions include dependency inferences, support for the universal relation concept, null value semantics, and an exploration of the properties of acyclic database schemes.
We define weakly commutative languages and periodic languages. We show that a language is regular if and only if it is simultaneously weakly commutative and periodic.
The problem of testing whether or not a context-free grammar possesses the LALR(k) property is studied. The uniform problem (i.e. both the subject grammar and the integer k are problem parameters) is shown to be complete for polynomial space (PSPACE) when k is expressed in unary, and complete for nondeterministic (one-level) exponential time (NE) when k is expressed in binary. This solves an open...
Bounding the size of deterministic left and right parsers for context-free grammars is studied. It is well-known that the size of an LR(k) parser is not always polynomially bounded in the size of the grammar. A similar non-polynomial size difference occurs also in LL(k) parsers. We show that such non-polynomial size differences cannot be regarded as a weakness of the LR(k) or LL(k) parser construction...
The problem of whether an arbitrary formula of Propositional Dynamic Logic (PDL) is deducible from a fixed axiom scheme of PDL is Π 11 -complete. This contrasts with the decidability of the problem when the axiom scheme is replaced by any single PDL formula.
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.