ECCC-Report TR99-008https://eccc.weizmann.ac.il/report/1999/008Comments and Revisions published for TR99-008en-usMon, 25 Apr 2011 14:19:58 +0300
Comment 1
| Correction to Theorem 7.3 |
Eric Allender,
Vikraman Arvind,
Meena Mahajan
https://eccc.weizmann.ac.il/report/1999/008#comment1The proof of Theorem 7.3 is buggy. This corrigendum gives a correct proof.Mon, 25 Apr 2011 14:19:58 +0300https://eccc.weizmann.ac.il/report/1999/008#comment1
Revision 1
| Arithmetic Complexity, Kleene Closure, and Formal Power Series |
Eric Allender,
Arvind V,
Meena Mahajan
https://eccc.weizmann.ac.il/report/1999/008#revision1Thu, 21 Mar 2002 00:00:00 +0200https://eccc.weizmann.ac.il/report/1999/008#revision1
Paper TR99-008
| Arithmetic Complexity, Kleene Closure, and Formal Power Series |
Eric Allender,
Vikraman Arvind,
Meena Mahajan
https://eccc.weizmann.ac.il/report/1999/008The 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.
Mon, 22 Mar 1999 17:20:05 +0200https://eccc.weizmann.ac.il/report/1999/008