Arithmetic complexity, Kleene closure, and formal power series

Eric Allender, V. Arvind, Meena Mahajan

Research output: Contribution to journalArticle

10 Citations (Scopus)

Abstract

The aim of this paper is to use formal power series techniques to study the structure of small arithmetic complexity classes such as GapNC1 and GapL. More precisely, we apply 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 GapNC1 and GapL. We prove that Kleene closure, inversion, and root extraction are all hard operations in the following sense: there is a language in AC0 for which inversion and root extraction are GapL-complete and Kleene closure is NLOG-complete, and there is a finite set for which inversion and root extraction are GapNC1 -complete and Kleene closure is NC1-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 GapNC1, such as GapAC0. 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. Some results in this paper show properties of complexity classes that are interesting independent of formal power series considerations, including some useful closure properties and complete problems for GapL.

Original languageEnglish (US)
Pages (from-to)303-328
Number of pages26
JournalTheory of Computing Systems
Volume36
Issue number4
DOIs
StatePublished - Jul 1 2003

Fingerprint

Formal Power Series
Inversion
Closure
Roots
Complexity Classes
Closure Properties
Reducibility
Monoids
Monoid
Finite Set
Counting
Internal
Language

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Cite this

Allender, Eric ; Arvind, V. ; Mahajan, Meena. / Arithmetic complexity, Kleene closure, and formal power series. In: Theory of Computing Systems. 2003 ; Vol. 36, No. 4. pp. 303-328.
@article{df4316732bad41a08e1e19ca94ce4bec,
title = "Arithmetic complexity, Kleene closure, and formal power series",
abstract = "The aim of this paper is to use formal power series techniques to study the structure of small arithmetic complexity classes such as GapNC1 and GapL. More precisely, we apply 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 GapNC1 and GapL. We prove that Kleene closure, inversion, and root extraction are all hard operations in the following sense: there is a language in AC0 for which inversion and root extraction are GapL-complete and Kleene closure is NLOG-complete, and there is a finite set for which inversion and root extraction are GapNC1 -complete and Kleene closure is NC1-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 GapNC1, such as GapAC0. 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. Some results in this paper show properties of complexity classes that are interesting independent of formal power series considerations, including some useful closure properties and complete problems for GapL.",
author = "Eric Allender and V. Arvind and Meena Mahajan",
year = "2003",
month = "7",
day = "1",
doi = "10.1007/s00224-003-1077-7",
language = "English (US)",
volume = "36",
pages = "303--328",
journal = "Theory of Computing Systems",
issn = "1432-4350",
publisher = "Springer New York",
number = "4",

}

Arithmetic complexity, Kleene closure, and formal power series. / Allender, Eric; Arvind, V.; Mahajan, Meena.

In: Theory of Computing Systems, Vol. 36, No. 4, 01.07.2003, p. 303-328.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Arithmetic complexity, Kleene closure, and formal power series

AU - Allender, Eric

AU - Arvind, V.

AU - Mahajan, Meena

PY - 2003/7/1

Y1 - 2003/7/1

N2 - The aim of this paper is to use formal power series techniques to study the structure of small arithmetic complexity classes such as GapNC1 and GapL. More precisely, we apply 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 GapNC1 and GapL. We prove that Kleene closure, inversion, and root extraction are all hard operations in the following sense: there is a language in AC0 for which inversion and root extraction are GapL-complete and Kleene closure is NLOG-complete, and there is a finite set for which inversion and root extraction are GapNC1 -complete and Kleene closure is NC1-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 GapNC1, such as GapAC0. 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. Some results in this paper show properties of complexity classes that are interesting independent of formal power series considerations, including some useful closure properties and complete problems for GapL.

AB - The aim of this paper is to use formal power series techniques to study the structure of small arithmetic complexity classes such as GapNC1 and GapL. More precisely, we apply 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 GapNC1 and GapL. We prove that Kleene closure, inversion, and root extraction are all hard operations in the following sense: there is a language in AC0 for which inversion and root extraction are GapL-complete and Kleene closure is NLOG-complete, and there is a finite set for which inversion and root extraction are GapNC1 -complete and Kleene closure is NC1-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 GapNC1, such as GapAC0. 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. Some results in this paper show properties of complexity classes that are interesting independent of formal power series considerations, including some useful closure properties and complete problems for GapL.

UR - http://www.scopus.com/inward/record.url?scp=0041993930&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0041993930&partnerID=8YFLogxK

U2 - 10.1007/s00224-003-1077-7

DO - 10.1007/s00224-003-1077-7

M3 - Article

AN - SCOPUS:0041993930

VL - 36

SP - 303

EP - 328

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 4

ER -