search In this paper, we explore the use of neighborhood search techniques for finding optimal solutions to the symmetric Traveling Salesman Problem. These techniques have been dramatically successful in obtaining near-optimal solutions to this problem for a reasonable expenditure of effort (1,2,3,4,5,6,9,10,12). Extensions of these techniques can be used to obtain the globally optimum solution, but the effort involved is at least an exponential function of the number of cities, n. Indeed, as this paper demonstrates, all local search algorithms that are capable of finding the optimal solution to an arbitrary n-city problem must grow at least as fast as

The synthesis of sequential machines by interconnections of copies of a fixed module is considered. A family of modules Mr,pfor positive integers r and p, is defined. Mr,p can be used to synthesize sequential machines with 2Pinput symbols. A nondeterministic sequential machine (NSM) is said to be r-bounded if it has one initial state and for no state and input are there more than r choices for the next state. It is shown that the problem of finding a network of modules Mr,prealizing a given event E is equivalent to finding an r-bounded NSM realizing the reverse of E. As a consequence, two upper bounds on the number of copies of the module Mr,pnecessary to realize an event E can be shown. 1) If E is defined by an n-state NSM, then E is defined by a network of at most cln2+plogr2copies of Mr,p. 2) If E is defined by an n-state deterministic sequential machine, then E is defined by a network of at most c2nl+vlogr2copies of Mr,p. cland C2are constants, about 4.

An algorithm for obtaining all simple disjunctive decompositions of a switching function is described. It operates on a function given as an expression using the operations AND, EXCLUSIVE OR, and complementation. It uses necessary conditions for the existence of a decomposition to eliminate sets of bound sets from consideration. Thus this technique differs from existing methods in that it attempts to test fewer bound sets at the expense of additional analysis. The algorithm can also be applied to functions given in a canonical form. It is shown that for a collection of functions of n variables chosen at random, the time required grows as n3. Previous methods, on the other hand, have an exponential growth rate.

The aim of this paper is to obtain a procedure for finding a minimum state nondeterministic finite automaton (NDA) equivalent to a given (in general, nondeterministic) finite automaton. Given a finite automaton A, we derive from A a matrix of 1' s and 0's, called a reduced automaton matrix RAM) of A, in a certain way and show that each state of A corresponds to a grid over the RAM. A grid consists of a set of rows and a set of columns of an RAM such that only 1's appear at the intersections. It is also shown that the union of all the grids, each of which corresponds to a state of A, covers all the 1 entries of an RAM.

In this note, we examine the problem of finding good state assignments when mixed memory type realizations (i.e., including mixtures of delay and trigger flip-flop memories) are permitted. Specifically, we describe situations that take advantage of this extra degree of design freedom, and we indicate how to modify two existing algorithms to determine such mixed realizations systematically.

Two errors have been found in the classical theory of two-level minimization of multiple-output switching networks. First, the prime implicant theorem must be modified to cover certain degenerate cases, and second, the widely accepted notion that there can always be found a miinimal network corresponding to a set of equations that are entirely sum-of-products or entirely product-of-sums is incorrect in a less trivial way, viz., sometimes the minimal network corresponds to a mixed representation (a set of equations some of which are products-of-sums and the remainder of which are sums-of-products). Counter examples are displayed to support these claims. Networks are exhibited in which AND gates feed AND gates.

In an early paper [1], McCluskey and Unger counted the number of distinct state assignments for synchronous sequential machines. Their formula, however, does not account for all distinct state assignments when the memory function in a realization is performed by delay elements alone. This note amends their formula by establishing the conditions for its validity and by deriving the appropriate expression under other conditions. An example illustrating the effect of using the McCluskey-Unger formula in a case where it does not apply can be found in a recent paper by Dolotta and McCluskey [2]. In their paper, a procedure is proposed for selecting a state assignment that has an associated economical realization. Their method implicitly restricts the memory units to be delay elements, and some distinct state assignments are not considered. Consequently, a number of realizations are over-looked. A minor modification in the Dolotta-McCluskey algorithm is suggested so that all distinct state assignments are taken into account. In some cases this revised procedure results in a more economical realization than the unmodified one.

The purpose of this paper is to describe an algorithmic ``solution'' to the assignment problem of synchronous sequential machines. The figure of merit used provides a mathematical evaluation of the reduced dependencies that may exist in the set of logic equations. If desired, the algorithm can assign the input, state, and output symbols of a given machine so as to ``minimize'' the total logic, i.e., reduced dependencies of both the state and output logic on state and input variables are optimized. The method is nonenumerative in the sense that the first assignmnent found is optimal. A restricted version of the algorithm has been programmed for an IBM 7094 computer.