A parallel alpha-beta search algorithm called unsynchronized iteratively deepening parallel alpha-beta search is described. The algorithm's simple control strategy and strong performance in complicated positions make it a viable alternative to the principal variation splitting algorithm (PVSA). Processors independently carry out iteratively deepening searches on separate subsets of moves. The iterative deepening is unsynchronized, e.g. one processor may be in the middle of the fifth iteration while another is in the middle of the sixth. Narrow windows diminish the importance of backing-up a score to the root of the tree as quickly as possible (one of the principal objectives of the PVSA). Speedups measured on one, two, four, and eight chess-playing computers are reported.>

A synchronous sequential machine realizable in the form of a loop-free circuit of trigger flip-flops and combinational gates is called a trigger machine. This paper studies the properties of this class of machines. Most importantly, canonical circuit forms and canonical algebraic representations are presented. Other basic properties of trigger machines, many of which closely parallel those of definite machines, are also presented. It is shown that the class of trigger machines forms a Boolean algebra and that, unlike definite machines, they are closed under reversal.

A procedure is presented for simplifying the flow table of a sequential machine M when, in addition to the given flow table, it is specified that certain input sequences cannot occur. It is assumed that M receives its input from the output of another machine M, and that the restricted sequences are therefore those sequences that M, cannot generate.

Universal modules are presented that can be used to realize any single input-single output synchronous sequential machine in the form of a circuit in which the input signal enters only one module. Additionally, no signal in the circuit fans out to more than some bounded number of terminals where the bound depends only on the module being used. Two different realization schemes are presented. The first scheme is based on the single feedback loop circuit model. Modules are connected in a highly regular array. Inputs to the last row of the array are constant logic signals. In the second scheme, a tree of modules is connected at the back to one or more one-hot reaiizations of a machine closely related to the machine being realized. The first scheme has the advantage of yielding a circuit with a highly regular interconnections pattern. The second scheme generally requires fewer modules. The theory is easily edxtended to machines with more than one input and output.

Synthesis techniques are presented for realizing an arbitrary synchronous flow table in the form of an array of identical modules interconnected in a regular pattern. Several types of structures and their corresponding modules are considered, and a relationship between these structures and earlier work on combinational circuits is shown.

An arbitrary sequential machine M may or may not be able to be decomposed into a series-parallel interconnection of two or more smaller machines. It seems natural to ask the following.

Gill[1]has shown that if there exists a finite-memory n-state sequential machine with finite memory μ, then μ cannot exceed ½n(n-1)ΔNn. He has further shown[2]that there exists an n-state Nninput-binary output machine with memory μ= Nnfor every n. The question of whether a tighter upper bound might be placed on μ by the order of the input alphabet was raised by Gill. Massey[3]recently has shown that there exists a ternary input-binary output finite-memory machine with memory μ=Nnfor every n. The primary purpose of this note is to show that for every n there exists an n-state binary input-binary output finite-memory machine with memory μ= Nn, and thus μ is shown not to be limited by the order of the input alphabet. It is shown that for every n there are actually at least two different machines with memory μ = Nn. It will also be shown that for every n there exists a binary input-binary output n-state finite-memory machine with μ = Nn-1.

Abstract—A "synthesis technique" is presented for "realizing" any arbitrary binary input-binary output "synchronous sequential Moore machine" in the form of a network composed of identical 2-state "component machines." With slight modification the synthesis technique presented can be used to realize any given n-input-p-output synchronous sequential Moore machine in the form of a network composed of identical 2-state component machines.