Revision #1 Authors: Eric Allender, Arvind V, Meena Mahajan

Accepted on: 21st March 2002 00:00

Downloads: 2166

Keywords:

TR99-008 Authors: Eric Allender, Vikraman Arvind, Meena Mahajan

Publication: 22nd March 1999 17:20

Downloads: 4548

Keywords:

The aim of this paper is to use formal power series techniques to

study the structure of small arithmetic complexity classes such as

GapNC^1 and GapL. More precisely, we apply the Kleene closure of

languages and the formal power series operations of inversion and

root extraction to these complexity classes. We define a counting

version of Kleene closure and show that it is intimately related to

inversion and root extraction within GapNC^1 and GapL. We prove

that Kleene closure, inversion, and root extraction are all hard

operations in the following sense: There is a language in AC^0 for

which inversion and root extraction are GapL-complete, and there is

a finite set for which inversion and root extraction are GapNC^1-

complete, with respect to appropriate reducibilities.

The latter result raises the question of classifying finite languages

so that their inverses fall within interesting subclasses of GapNC^1,

such as GapAC^0. We initiate work in this direction by classifying 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.

Comment #1 Authors: Eric Allender, Vikraman Arvind, Meena Mahajan

Accepted on: 25th April 2011 14:19

Downloads: 3133

Keywords:

The proof of Theorem 7.3 is buggy. This corrigendum gives a correct proof.