We show that the recognition problem of context-free languages can be reduced to
membership in the language defined by a regular expression with intersection by a log …

We present a combinatorial interpretation of Berkowitz's algorithm. Berkowitz's algorithm is
the fastest known parallel algorithm for computing the characteristic polynomial of a matrix …

We survey some relationships between computational complexity and neural network
theory. Here, only networks of binary threshold neurons are considered. We begin by …

This paper deals with the problem of signal compression by linearly expanding the signal to
be compressed along the elements of an overcomplete dictionary. The compression is …

Com o objetivo de desenvolver uma fundamentação teórica para o estudo formal de
problemas de otimização NP-difíceis, focalizando sobre as propriedades estruturais desses …

We present a new complexity theoretic approach to real-time computations. We define timed
ω-languages as a new formal model for such computations, that we believe to allow a …

We investigate the complexity of enumerative approximation of two elementary problems in
linear algebra, computing the rank and the determinant of a matrix. In particular, we show …

We identify the class of optimization problem expressible as independence systems that can
be solved in real time using a parallel machine with polynomially bounded resources as …

We give an overview of the computational complexity of linear and mesh-connected cellular
and iterative arrays with respect to well known models of sequential and parallel …