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.
We propose a model for the concurrent read exclusive write PRAM that captures its communication and computational requirements. For this model, we present several results, including the following: Two n×n matrices can be multiplied in O(n3/p) computation time and O(n2/p2/3) communication delay using p processors (for p≤n3 / log3/2n). Furthermore,...
The aim of this study is three-fold: (1) to study the class of computable functionals on uninterpreted domains, and the machines (or program schemes) on which such functionals can be computed, (2) to unify the notion of the interpretation for a program schema with the notion of the data structures which the schema uses, and (3) to unify a large number of the classes of program schemas considered by...
A prefix-or circuit has n inputs and n outputs; the ith output is the OR of the first i inputs. A prefix-carry circuit has 2n inputs, interpreted as two n-bit numbers, and n outputs; the ith output is the carry in the ith position of the sum of the two numbers. We show a nonlinear lower bound for constant-depth, unboundedfanin implementations of prefix-or. However, with negation, linear size circuits...
In this paper we introduce a model of Hierarchical Memory with Block Transfer (BT for short). It is like a random access machine, except that access to location x takes time f(x), and a block of consecutive locations can be copied from memory to memory, taking one unit of time per element after the initial access time. We first study the model with f(x) = xα for 0 ≪ α ≪ 1. A tight bound of θ(n log...
A complexity theory for unbounded fan-in parallelism is developed where the complexity measure is the simultaneous measure (number of processors, parallel time). Two models of unbounded fan-in parallelism are (1) parallel random access machines that allow simultaneous reading from or writing to the same common memory location, and (2) circuits containing AND's, OR's and NOT's with no bound placed...
This paper is an attempt at laying the foundations for the classification of queries on relational data bases according to their structure and their computational complexity. Using the operations of composition and fixpoints, a Σ-Π hierarchy of height, ω2, called the fixpoint query hierarchy, is defined, and its properties investigated. The hierarchy includes most of the queries considered in the...
Functions computed on nondeterministic machines consist of two parts. The halting part which consists of outputs of halting computations, is, as expected, recursively enumerable. The divergence part, which consists of inputs for which diverging computations are possible, can however be any set in Σ11. Such highly noncomputable sets arise if one admits the "finite delay property". This implies...
We define alternating Turing Machines which are like nondeterministic Turing Machines, except that existential and universal quantifiers alternate. Alternation links up time and space complexities rather well, in that alternating polynomial time equals deterministic polynomial space, and alternating linear space equals deterministic exponential time. Such considerations lead to a two-person game complete...
A linear recursive program consists of a set of procedures where each procedure can make at most one recursive call. The conventional stack implementation of recursion requires time and space both proportional to n, the depth of recursion. It is shown that in order to implement linear recursion so as to execute in time n one does not need space proportional to n : ne for arbitrarily small e will do...
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.