It is possible to compute gcd $(x, y)$ efficiently with only $O(\log xy)$ additions and subtractions, when three arithmetic registers are available but not when there are only two. Several other functions, such as $x^y \bmod z$, are also efficiently computable in a small number of registers, using only addition, subtraction, and comparison.

The design of integrated cLrcuJts to Implement arbitrary regular expressions is considered In general, a regular expression with n operands may be converted into a nondetermmlstlc fimte automaton with at most n states and n trans~uons Instead of converting the nondetermtntsttc device to a determm~suc one, two ways of implementing the nondetermlnistlc dewce directly are proposed.One approach is to produce a PLA (programmable logic array) of approximate dimensions n rows and 2n columns by representing the states of the nondetermm~stlc fimte automaton directly by columns This approach, whde theoreucally suboptimal, makes use of carefully developed technology and, because of the care with which PLA implementation has been done, may be the preferred techmque m many real sttuatlons Another approach ~s to use the hierarchical structure of the automaton produced from the regular expression by the McNaughton-Yamada algorithm to grade a hierarchical layout of the ctrcmt.This method produces a clrcmt O(x/-~n) on a side and ~s, to w~thin a constant factor, the best that can be done m general Categories and Subject Descriptors: B 1 2 [Control Structures and Microprogramming]: Control Structure Performance Analysis and Design Aids--automatic synthesis, formal models; B.7 2 [Integrated Circuits]: Destgn Aids-

We consider the design of integrated circuits to implement arbitrary regular expressions. In general, we may use the McNaughton-Yamada algorithm to convert a regular expression of length n into a nondeterministic finite automaton with at most 2n states and 4n transitions. Instead of converting the nondeterministic device to a deterministic one, we propose two ways of implementing the nondeterministic device directly. First, we could produce a PLA (programmable logic array) of approximate dimensions 4n × 4n by representing the states directly by columns, rather than coding the states in binary. This approach, while theoretically suboptimal, makes use of carefully developed technology and, because of the care with which PLA implementation has been done, may be the preferred technique in many real situations. Another approach is to use the hierarchical structure of the automaton produced from the regular expression to guide a hierarchical layout of the circuit. This method produces a circuit 0(√n) on a side and is, to within a constant factor, the best that can be done in general.

In this paper we consider the question of how much space is needed to represent a set. Given a finite universe U and some subset V (called the vocabulary), an exact membership tester is a procedure that for each element s in U determines if s is in V. An approximate membership tester is allowed to make mistakes: we require that the membership tester correctly accepts every element of V, but we allow it to also accept a small fraction of the elements of U - V.

New upper and lower bounds are presented for the maximum number of comparisons, f(i,n), required to select the i-th largest of n numbers. An upper bound is found, by an analysis of a new selection algorithm, to be a linear function of n:

A special purpose theorem prover for establishing the validity of expressions over integer variables was developed as part of a program verifier. It is built around a powerful system for manipulating and simplifying integer expressions.

Programs to solve combinatorial search problems may often be simply written by using multiple-valued functions. Such programs, although impossible to execute directly on conventional computers, may be converted in a mechanical way into conventional backtracking programs. The process is illustrated with algorithms to find all solutions to the eight queens problem on the chessboard, and to find all simple cycles in a network.

The syntactic rules for many programming languages have been expressed by formal grammars, generally variants of phrase-structure grammars. The syntactic analysis essential to translation of programming languages can be done entirely mechanically for such languages. Major problems remain in rendering analyzers efficient in use of space and time and in finding fully satisfactory formal grammars for present and future programming languages.

Syntactic Analysis and Operatm• Precedence*RoBERT "\V.FLoYD libstmct.Three increasingly restricted types of formal grammar are phrase structure grammars, operator grammars and precedence grammars.Precedence grammars form models of mathematical and algorithmic languages which may Le analyzed mechanically by a simple procedure based on a matrix representation of a relation between character pairs.

article Free AccessA Descriptive Language for Symbol Manipulation Author: Robert W. Floyd Armour Research Foundation of Illinois Institute of Technology, Chicago, Illinois Armour Research Foundation of Illinois Institute of Technology, Chicago, IllinoisView Profile Authors Info & Claims Journal of the ACMVolume 8Issue 4pp 579–584https://doi.org/10.1145/321088.321096Published:01 October 1961Publication History 63citation676DownloadsMetricsTotal Citations63Total Downloads676Last 12 Months80Last 6 weeks11 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF