The authors give a very simple uniform explanation of the persistence of exponential decidability. They follow M. Vardi and P. Wolper's theory (1986) that given a formula gamma of a temporal or dynamic logic, it is important to construct an equivalent automation M/sub gamma /. They characterize the weak monadic theory of the tree; it turns out that weak alternating automata greatly simplify design procedures.>

We have discovered a very strong connection between certain areas of theoretical computer science—the theory of context-free languages and pushdown automata, tiling problems, cellular automata, and vector addition systems—and certain concepts from group theory, topology, and second-order logic. We use these concepts to investigate a rather wide class of graphs which we call context-free graphs. Using the results obtained and Rabin's theorem that the monadic second-order theory of the infinite binary tree is decidable, we are able to show that the monadic second-order theory of any context-free graph is decidable. Cellular automata and vector addition systems are usually considered as involving the grid of integer lattice points in n-dimensional space. We show that such systems make sense on a very general class of graphs and, in contrast to the classical case, all the relevant algorithmic problems concerning such systems are solvable on context-free graphs.

In this paper we presentt family of techniques for the design of combinational networks whose objective is the reduction of the number of levels, subject to a constraint on the fan-in of the logic gates. We show that a Boolean expression with n literals and involving the connectivest AND and OR can be restructured so that the resulting network of AND and OR gates has depth at most Cllog2n + δ, where alis 1.81, 1.38, 1.18, and 1 for maximum fan-in l of 2,3,4, and 5, respectively. If we additionally require that the amount of equipment of the resulting network be bounded by a linear function of n, it is possible to bound the depth by 2 log2n with a fan-in of at most 3.

Let E be an arithmetic expression involving n variables, each of which appears just once, and the possible operations of addition, multiplication, and division. Although other cases are considered, when these three operations take unit time the restructuring algorithms presented in this paper yield evaluation times no greater than 2.88 log 2 n + 1 and 2.08 log 2 n for general expressions and division-free expressions, respectively. The coefficients are precisely given by 2/log 2 α ≈ 2.88 and 1/log 2 β ≈ 2.08, where α and β are the positive real roots of the equations z 2 = z + 1 and z 4 = 2 z + 1, respectively. While these times were known to be of order log 2 n , the best previously known coefficients were 4 and 2.15 for the two cases. The authors conjecture that the present coefficients are the best possible, since they have exhibited expressions which seem to require these times within an additive constant. The paper also gives upper bounds to the restructuring time of a given expression E and to the number of processors required for its parallel evaluation. It is shown that at most O (n 1.44 ) and O (n 1.82 ) operations are needed for restructuring general expressions and division-free expression, respectively. It is pointed out that, since the order of the compiling time is greater than n log n , the numbers of required processors exhibit the same rate of growth in n as the corresponding compiling times.

A Boolean expression wilth n literals, i.e., n distinct appearances of variables, can be evaluated by a parallel processing system in at most 1.81 log2n steps, or, equivalently, by a network constructed with two-input AND and OR gates and having at most 1.81 log2n levels.

A network which sorts n numbers, when used to sort numbers of only two sizes, 0 and 1, can be regarded as forming the n frontal (unite) symmetric Boolean functions of n arguments When sorting networks are constructed from comparator modules they have been widely conjectured to require (1) delay time or number of levels of order (log2n) 2, (2) size or number of elements of order n0og2n) ~, and (3) formula length or number of hterals of order n~°*2 ~ It IS proved constructively in the paper that, if one permits the use of negations in constructing the corresponding Boolean functions, these three measures of complexity can be reduced to the orders of log2n, n, and n ~, respectively The latter network, however, is Incapable of sorting numbers other than O's and rs and may be thought of as merely counting the number of Inputs which are 1 It is shown, however, that one may incorporate this network in a larger network which does sort and In time proportional to only logan This network is the first known example of a nonadaptive network capable of sorting in time less than (log2n) 2 CR CATEGORIES: 5 25, 5 31, 6 1 KEY WORDS AND PHRASES computational complexity, sorting, counting, symmetric Boolean functions, computation time, length of formula 1.Two basic operations often used in sorting networks are the formation of the maximum and the minimum of a pair of numbers.These operations are usually performed at the same time by a two-input, two-output device called a comparator module which may be regarded as being composed of two more basic elements.The first is a comparison element with binary output indicating which of the two inputs is larger, and the second is a crossover switch which is set by the output of the first element so as to place the larger number on one line and the smaller on the other.We may use the Boolean notation a V b and ab for the maximum and the minimum, respectively, of two numbers a and b.The convenience of this notation has been observed by several authors [1, 3], since Boolean expressions can be used in the analysis of sorting networks.The interpretation of these expressions, however, depends upon the domain of the variables.A network of comparator modules sorts n numbers if and only if, when interpreted as a network of AND and OR gates, it realizes the n frontal (unite) symmetric Boolean functions of n variables [3].This fact is easily seen, since a sorting network can also be used with numbers which are of just two sizes, 0 and 1.Conversely, if all input configurations of O's and l's are properly sorted, the output functions are uniquely defined as the frontal symmetric functions.These functions are also the ones which, when reinterpreted as ap-

Using as logic modules two-input one-output arbitrary logic gates, this note considers the problem of the longest chain (number of levels) in a tree-type interconnection realizing a Boolean function of n variables. Specifically, we are interested in the minimum number of levels L(n) by which we can constructively realize all Boolean functions of n variables. It was previously shown that L(n)≤n for n=3, 4 and it was so conjectured for n= 5; in this note we are able to show that this holds for n=5, 6, 7, 8.

If we regard reversibility (in the intuitive sense) as the ability to return to a previous state, automata possess varying types and degrees of reversibility.Several properties of automata are defined, each describing a type of connectivity or reversibility.Their relative strengths are considered, as well as whether they are preserved under generalized homomorphisms.It is shown that in the case of finite automata five of these properties are equivalent.The reverse, Rev(A), of an automaton A is defined and its relationship to A is studied.

The complexity of an electronic switching circuit is defined in a sufficiently general way so that most definitions which are presently used may be included. If ø(p, q) is the complexity of a p input q output circuit which has been minimized then we may define E(p, q) as the maximum of ø(p, q) over all p input, q output circuits. In spite of the generality of the definition of complexity one may obtain the following inequality which gives upper and lower bounds on this maximum complexity: C12r/r≦E(p, q)≦C22r/r where r = p+log2q. In this expression C1and C2are constants independent of p and q which depend upon the definition of complexity. These theoretical bounds are compared with those obtained from a few known circuiit designs.

A solution is sought to the general problem of simplifying switching circuits that have more than one output. The mathematical treatment of the problem applies only to circuits that may be represented by “polynomials” in Boolean algebra. It is shown that certain parts of the multiple output problem for such circuits may be reduced to a single output problem whose inputs are equal in number to the sum of the numbers of inputs and outputs in the original problem. A particularly simple reduction may be effected in the case of two outputs. Various techniques are described for simplifying Boolean expressions, called “+ polynomials,” in which the operation “exclusive or” appears between terms. The methods described are particularly suitable for use with an automatic computer, and have been tested on the Illiac. An unexpected metric relationship is shown to exist between the members of certain classes of “+ polynomials” called “nets.” This relationship may be used for constructing error-detecting codes, provided the number of bits in the code is a power of two.