DIMACS TR: 97-61

Arithmetic Complexity, Kleene Closure, and Formal Power Series



Authors: Eric Allender, V Arvind, and Meena Mahajan

ABSTRACT

In this paper we show how two fundamental operations used in formal language theory provide useful tools for the investigation of arithmetic complexity classes. More precisely, we use Kleene closure of languages and inversion of formal power series to investigate subclasses of the complexity class GapL. GapL is the complexity class that characterizes the complexity of computing the determinant; it corresponds to counting the number of accepting and rejecting paths of nondeterministic logspace-bounded Turing machines.) We define a counting version of Kleene closure and show that it is intimately related to inversion within the complexity classes GapL and GapNC^1. In particular, we prove that Kleene closure and inversion are both hard operations in the following sense

Furthermore, we classify the complexity of the Kleene closure of finite languages. We formulate the problem in terms of finite monoids and relate its complexity to the internal structure of the monoid.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-61.ps.gz


DIMACS Home Page