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.
The present paper shows how to construct a maximum matching in a bipartite graph with n vertices and m edges in a number of computation steps proportional to (m+n) n.
A rectangular logic array is described which can realize any combinational switching function. Straight-forward analysis and synthesis procedures are described and the realizations of a number of special functions are given. These include threshold functions, parity functions, symmetric functions, and universal logic functions. Other properties of the array which are examined include diagnostic procedures,...
This paper presents a synthesis method to realize any p-state normal asynchronous sequential circuit A according to an unconventional structure. It consists of two critical-race free S.T.T. normal asynchronous circuits A1 and A2 connected in series, where A1 is realized with L internal variables and A2 with 2 ?? So internal variables (So = [ log2 p] ). It is shown that L = 1 for circuit A with single...
In order to obtain a short fault-detection sequence for a sequential machine, the concept of an easily testable machine is introduced. Such a machine is one which possesses a minimal-length homogeneous distinguishing sequence and requires no transfer sequences in the fault-detection sequence. A design procedure is presented in which an arbitrary machine is embedded in an easily testable machine by...
Universal base functions (UBF's) are defined which are generalizations of universal logic functions. An (n, m, r)-UBF can be implemented as a single module (UBM) with n+m inputs and 1 output. An arbitrary n-variable switching function fn (X) is then realized on the fixed UBM by realizing a suitable set of m r-variable functions with which to drive m inputs of the UBM, the remaining n inputs being...
This paper investigates the properties and utilizations of one- and two-dimensional NAND gate cellular arrays. Both irredundant and redundant one-dimensional cascades are investigated. The cascade's output function is obtained in closed form, and a test and synthesis procedure is developed. Both irredundant and redundant two-dimensional arrays are examined, and an arbitrary two-dimensional array is...
The value of depth-first search or "backtracking" as a technique for solving graph problems is illustrated by two examples. An algorithm for finding the biconnected components of an undirected graph and an improved version of an algorithm for finding the strongly connected components of a directed graph are presented. The space and time requirements of both algorithms are bounded by k1V...
LR-regular grammars are defined similarly to Knuth's LR(k) grammars, with the following exception. Arbitrarily long look-ahead is allowed before making a parsing decision during the bottom-up syntactical analysis; however, this look-ahead is restricted in that the essential "lookahead information" can be represented by a finite number of regular sets, thus can be computed by a finite state...
Arithmetic operations on matrices are applied to the problem of finding the transitive closure of a Boolean matrix. The best transitive closure algorithm known, due to Munro, is based on the matrix multiplication method of Strassen. We show that his method requires at most O(nα ?? P(n)) bitwise operations, where α = log27 and P(n) bounds the number of bitwise operations needed for arithmetic modulo...
In this paper it is shown that by suitably modifying Garner's algorithm for applying the Chinese Remainder Theorem to optimally employ the fast multiplication techniques of Schönhage and Strassen, one can often decrease the computing time of algebraic algorithms employing modular (congruence, residue) arithmetic.
This paper presents a self-contained and more elementary treatment of our mathematical theory of the syntax and semantics of language developed in [W-1] and [ W-2]. It applies this theory to the definition of subsets, and operators on subsets of the carrier of algebras. We show how regular and context-free sets of strings, recognizable sets of trees, and recursively enumerable (r.e.) sets of natural...
We define the following classes of program schemata: P = class of schemes using a finite number of simple variables PA = class of schemes using simple and subscripted variables (arrays) PR = class of schemes allowing recursive functions PL = class of schemes allowing labels as values Pm = class of schemes allowing a finite number of special markers as values Ppds = class of schemes using pushdown...
This note is concerned with the number of binary comparisons required to compute the maximum or the median of sets of numbers. The new results are: (a) the maximum of a set of n integers cannot be computed in fewer than n-1 comparisons if comparisons of only linear functions of the integers are permitted, but the maximum can be computed in log2 n comparisons if comparisons can be made between exponential...
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.