In this paper we show several results about monotone planar circuits. We show that monotone planar circuits of bounded width, with access to negated input variables, compute exactly the functions in non-uniform AC/sup 0/. This provides a striking contrast to the non-planar case, where exactly NC/sup 1/ is computed. We show that the circuit value problem for monotone planar circuits, with inputs on the outerface only, can be solved in LOGDCFL/spl sube/SC, improving a LOGCFL upper bound due to Dymond and Cook. We show that for monotone planar circuits, with inputs on the outerface only, excessive depth compared to width is useless; any function computed by a monotone planar circuit of width w with inputs on the outerface can be computed by a monotone planar circuit of width O(w) and depth w/sup O(1)/. Finally, we show that monotone planar read-once circuits, with inputs on the outerface only, can be efficiently learned using membership queries.

We prove that at least 3k−4/k(2k−3)(n/2) – O(k)equivalence tests and no more than 2/k (n/2) + O(n) equivalence tests are needed in the worst case to identify the equivalence classes with at least k members in set of n elements. The upper bound is an

We show that searching a width k maze is complete for Pi_k, i.e., for the k'th level of the AC0 hierarchy. Equivalently, st-connectivity for width k grid graphs is complete for Pi_k. As an application, we show that there is a data structure solving dynamic st-connectivity for constant width grid graphs with time bound O(log log n) per operation on a random access machine. The dynamic algorithm is derived from the parallel one in an indirect way using algebraic tools.

Let M be a fixed finite monoid.We consider the problem of implementing a data type containing a vector x ϭ ( x 1 , x 2 , . . ., x n ) ʦ M n , initially (1, 1, . . ., 1), with two kinds of operations, for each i ʦ {1, . . ., n} and a ʦ M, an operation change i,a which changes x i to a and a single operation product returning ͟ iϭ1 n x i .This is the dynamic word problem for M. If we in addition for each j ʦ {1, . . ., n} have an operation prefix j returning ͟ iϭ1 j x i , we get the dynamic prefix problem for M. We analyze the complexity of these problems in the cell probe or decision assignment tree model for two natural cell sizes, 1 bit and log n bits.We obtain a partial classification of the complexity based on algebraic properties of M.

Let M be a fixed finite monoid. We consider the problem of implementing a data type containing a vector x=(x/sub 1/,x/sub 2/,...,x/sub n/)/spl isin/M/sup n/, initially (1,1,...,1) with two kinds of operations, for each i/spl isin/{1,...,n}, a/spl isin/M, an operation change/sub i,a/ which changes x/sub i/ to a and a single operation product returning /spl Pi//sub i=1//sup n/x/sub i/. This is the dynamic word problem. If we in addition for each j/spl isin/{1,...,n} have an operation prefix/sub j/ returning /spl Pi//sub i=1//sup j/x/sub i/, we talk about the dynamic prefix problem. We analyze the complexity of these problems in the cell probe or decision assignment tree model for two natural cell sizes, 1 bit and log n bits. We obtain a classification of the complexity based on algebraic properties of M.>

A projection of a Boolean function is a function obtained by substituting for each of its variables a variable, the negation of a variable, or a constant. Reducibilities among computational problems under this relation of projection are considered. It is shown that much of what is of everyday relevance in Turing-machine-based complexity theory can be replicated easily and naturally in this elementary framework. Finer distinctions about the computational relationships among natural problems can be made than in previous formulations and some negative results are proved.

A construction is presented which, given a fixed undirected graph of low degree and small average path length, yields an infinite sequence of low diameter graphs of increasing order and fixed degree. As examples of the construction, infinite sequences of low diameter graphs are presented with degrees in the range 3 to 30. Expressed as a function of the order of the graphs, the degree 3 sequence has diameter bounded above by 1.4722 log2 N + O(1), and the degree 4 sequence by 0.9083 log2N + O(1).

It is shown that any multivariate polynomial of degree d that can be computed sequentially in C steps can be computed in parallel in $O((\log d)(\log C + \log d))$ steps using only $(Cd)^{O(1)} $ processors.

A projection of a Boolean function is a function obtained by substituting for each of its variables a variable, the negation of a variable, or a constant. Reducibilities among computational problems under this relation of projection are considered. It is shown that much of what is of everyday relevance in Turing-machine-based complexity theory can be replicated easily and naturally in this elementary framework. Finer distinctions about the computational relationships among natural problems can be made than in previous formulations and some negative results are proved.

In [Math. Systems Theory, 13 (1979), pp. 29–43], the authors obtained a number of upper and lower bounds for various problems concerning L-systems. In most cases the bounds were rather close; however, for general $D0L$ membership the upper bound was $\mathcal{P}$, and the lower was deterministic log space. In this note we show that membership can be decided deterministically in $\log ^2 n$ space, which makes it very unlikely that the problem is complete for $\mathcal{P}$. We also show that nonmembership is as hard as any problem solvable in nondeterministic log n space. This is an improved lower bound unless ${\textbf{DSPACE}}(\log n) = {\textbf{NSPACE}}(\log n)$, which is also thought to be very unlikely.

In this paper we give a method for decomposing subclasses of different families of languages, parallel in nature, into other families. These decomposition theorems can be used to produce languages not it a family by using examples of languages not belonging to some “smaller” family.

In this paper we give a method for decomposing subclasses of different families of languages, into other possibly smaller families. This method can be used to produce languages not in a family by using known examples of languages not belonging to other families.