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.
Let U1,U2,...,Udbe totally ordered sets and let V be a set of n d-dimensional vectors in U1× U2× ... × Ud. A partial ordering is defined on V in a natural way. We consider the problem of finding all maximal elements of V with respect to the partial ordering. The computational complexity of the problem is defined to be the maximum number of required comparisons of two components and is denoted by Cd(n)...
We investigate the complexity of network selection by measuring it in terms of U(t,N), the minimum number of comparators needed, and T(t,N), the minimum delay time possible, for networks selecting the smallest t elements from a set of N inputs. New bounds on U(t,N) and T(t,N) are presented. In particular, U(3,N) is determined to within a constant of 2, and asymptotic formulae for U(t,N) and T(t,N)...
We examine the efficiency of generalized hash-coding algorithms for performing partial-match searches of a random-access file of binary words. A precise characterization is given of those hash functions which minimize the average number of buckets examined for a search; and a new class of combinatorial designs is introduced which permits the construction of hash functions with worst-case behavior...
A system of flowchart program schemata is viewed as a schema for a class of natural computational complexity measures. Certain properties of this class of measures, such as recursive enumerability of complexity classes and a weak notion of "conformity", are shown to derive from the schematic structure. Other properties, earlier proposed as "natural", are shown to be more superficial,...
The equivalence problem for languages accepted by deterministic pushdown automata is shown to be decidable if and only if the strong equivalence problem for monadic recursion schemes is decidable. The proof is obtained through a series of reductions, and several different classes of acceptors are introduced.
This paper proves a conjecture of Meyer and Stockmeyer, that the equivalence problem of regular expressions over one letter alphabets, with the operations of union, concatenation, Kleene star, negation and squaring, is solvable in elementary time and space. This is done by reduction of this problem to Presburger Arithmetic, making use of an algorithm presented by Oppen.
Several polynomial time algorithms finding "good," but not necessarily optimal, tours for the traveling salesman problem are considered. For the nearest neighbor method, the worst case ratio of the obtained tour to the optimal tour is shown to increase logarithmically with the number of cities. For another method, which we call the nearest insertion method, the worst case ratio is shown...