We study the complexity of algorithmic problems for matrices that are represented by multi-terminal decision diagrams (MTDD). These are a variant of ordered decision diagrams, where the terminal nodes are labeled with arbitrary elements of a semiring (instead of 0 and 1). A simple example shows that the product of two MTDD-represented matrices cannot be represented by an MTDD of polynomial size. To overcome this deficiency, we extended MTDDs to MTDD_+ by allowing componentwise symbolic addition of variables (of the same dimension) in rules. It is shown that accessing an entry, equality checking, matrix multiplication, and other basic matrix operations can be solved in polynomial time for MTDD_+-represented matrices. On the other hand, testing whether the determinant of a MTDD-represented matrix vanishes PSPACE$-complete, and the same problem is NP-complete for MTDD_+-represented diagonal matrices. Computing a specific entry in a product of MTDD-represented matrices is #P-complete.
Let us finally mention that straight-line programs are also used for the compact representation of other objects, e.g. polynomials @cite_34 , trees @cite_31 , graphs @cite_32 , and regular languages @cite_16 .
@cite_31 @cite_34 @cite_32 @cite_16
2148149459 2011758726 2021380921 2029153962
The complexity of various membership problems for tree automata on compressed trees is analyzed. Two compressed representations are considered: dags, which allow to share identical subtrees in a tree, and straight-line context-free tree grammars, which moreover allow to share identical intermediate parts in a tree. Several completeness results for the classes NL, P, and PSPACE are obtained. Finally, the complexity of the evaluation problem for (structural) XPath queries on trees that are compressed via straight-line context-free tree grammars is investigated. Let Q be any algebraic structure and the set of all total programs over Q using the instruction set z ,,-1, z , , x + y, z ,,-x y , z x * y , z -x y . (A program is total if no division by zero occurs during any computation ) Let the equivalence problem for be the problem of deciding for two given programs in whether or not they compute the same funcuon The following results are proved: (1) If Q is an inftmte field (e.g, the rauonal numbers or the complex numbers), then the equwalence problem for is probabilistlcally decidable in polynomml time. The result also holds for programs with no dwlslon instructions and Q an infimte integral domain (e.g., the integers). (2) If Q is a finite field, or if Q is a fimte set of integers of cardmahty _>2, then the equivalence problem is NP-hard. The case when the field Q is finite but its cardinality is a funcuon of the size of the instance to the eqmvalence problem is also considered An example is shown for which a sharp boundary between the classes NP-hard and probabihsticaUy decidable exists (provided they are not identical classes). In [Le 82, Le 85, Le 86a, Le 86b] a hierarchical graph model is discussed that allows to exploit the hierarchical description of the graphs for the efficient solution of graph problems. The model is motivated by applications in CAD, and is based on a special form of a graph grammar. The above references contain polynomial time solutions for the hierarchical versions of many classical graph problems. However, there are also graph problems that cannot benefit from the succinctness of hierarchical description of the graphs. We consider two formalisms for representing regular languages: constant height pushdown automata and straight line programs for regular expressions. We constructively prove that their sizes are polynomially related. Comparing them with the sizes of finite state automata and regular expressions, we obtain optimal exponential and double exponential gaps, i.e., a more concise representation of regular languages.