1-4hit |
The notion of alternating context-free grammar (ACFG for short) was introduced by Moriya in 1989. In this paper, we study the relationships between some complexity classes and the classes of languages generated by restricted types of ACFG's. Two restricted types of ACFG's considered are linear ACFG's and ε-free ACFG's. For an ACFG G, let Lleft (G) denote the language of terminal strings generated by leftmost derivations in G. Let {Lleft (G)G is an ε-free ACFG} and ACFLlinear{Lleft (G)G is a linear ACFG's}. The main results of the present paper are as follows:(1) the class of languages that are log-space many-one reducible to languages in ACFLlinear is equivalent to P, and(2) the class of languages that are log-space many-one reducible to languages in is equivalent to PSPACE.
In this paper, some classes of arithmetic circuits are introduced that capture the computational complexity of computing the determinant of matrices with entries either indeterminates or constants from a field. An arithmetic circuit is just like a Boolean circuit, except that all AND and OR gates (with fan-in two) are replaced by gates realizing a multiplication and an addition, respectively, of two polynomials over some indeterminates with coefficients from the field, and the circuit computes a (formal multivariate) polynomial in the obvious sense. An arithmetic circuit is said to be skew if at least one of the inputs of each multiplication gate is either an indeterminate or a constant. Then it is shown that for all square matrices M of dimension q, the determinant of M can be computed by a skew arithmetic circuit of
We sketch two algorithms that solve the undirected st-connectivity problem in a small amount of space. One is due to Nisan, Szemeredy and Wigderson, and takes space O(log3/2n), where n denotes the number of nodes in a give undirected graph. This is the first algorithm that overcame the Savitch barrier on the space complexity of the problem. The other is due to Tarui and this author, and takes space O(sw(G)2 log2 n), where sw(G) denotes the separation-width of a given graph G. Their result implies that the st-connectivity problem can be solved in logarithmic space for any class of graphs with separation-width bounded above by a predetermined constant. This class is one of few nontrivial classes for which the st-connectivity problem can be solved in logarithmic space.
It is known that any chordal graph can be uniquely decomposed into simplicial components. Based on this fact, it is shown that for a given chordal graph, its automorphism group can be computed in O((c!n)O(1)) time, where c denotes the maximum size of simplicial components and n denotes the number of nodes. It is also shown that isomorphism of those chordal graphs can be decided within the same time bound. From the viewpoint of polynomial-time computability, our result strictly strengthens the previous ones respecting the clique number.