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.
Given a particular computer system the extension problem concerns the prediction of performance when the size of main memory is increased. In this paper a specific approach to this problem is formulated for demand paging systems. A necessary and sufficient condition on the nature of page replacement rules which leads to solutions of the extension problem is a major result of the paper. As the other...
Theoretical properties of computer programs have been the object of considerable study in recent years. In this paper we consider the problem of joining - or composing - one program with another. We study basic properties of compositions within a theoretical model for parallel computation which is closely related to parallel program schemata. In particular, we introduce the notion of finishing schemata...
The high level languages here are simplified programming languages focussing attention on various facilities such as recursion and pushdown stores. They are assumed to have some kind of subroutine facility. The notion of power studied is obtained by treating the programs as presenting functions of variable sub-routines and arguments of arbitrary data type. Languages are exhibited which are capable...
Let Σ be a finite alphabet, Σ* the free monoid generated by Σ and |x| the length of x ε Σ*. For any integer k ≥ 0, fk(x)(tk (x)) is x if |x| ≪ k+1, and it is the prefix (suffix) of x of length k, otherwise. Also let mk+1 (x) = {v|x = uvw and |v| = k+1}. For x,y ε Σ* define x ∼k+1y iff fk(x) = fk(y), tk(x) = tk(y) and mk+1(x) = mk+1 (y). The relation ∼k+1 is a congruence of finite index over Σ*. An...
A physico-mathematical basis is used to establish bounds TD(n) on the time needed to compute n-argument functions by spatially distributed primitive devices or composite systems D. The axioms used concern the speed, packing density and noise threshold of the energy with which any computing device detects or alters the physical representation of information. The principal result is that TD(n) grows...
Families of languages recognized by multi-head writing finite automata are considered. For n≥1, an n-head writing finite automaton (n-wfa) is a finite state device with n one-way read-write heads on a single input tape. Relationships between families of languages recognized by n-wfa (Wn) and other models (e.g. n-head nonwriting finite automata, linear-bounded automata, and real-time buffer automata)...
A formal study of pattern recognition capabilities of cellular automata is undertaken based on a class of recently introduced grammars for two dimensions, the array grammars, which can be thought of as the two-dimensional generalization of context-sensitive grammars. The class of languages (patterns) generated by array grammars is shown to be precisely the class of languages accepted by cellular automata...
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.