Arithmetic Complexity, Kleene Closure, and Formal Power Series
Arithmetic Complexity, Kleene Closure, and Formal Power Series
复制标题
算术复杂度、克林闭包和形式幂级数
DOI：
--
复制
发表时间：
1997
影响因子：
0.5
通讯作者：
M. Mahajan
中科院分区：
文献类型：
--
作者：
Eric Allender;V. Arvind;M. Mahajan
抽象的。本文的目的是使用形式幂级数技术来研究小的算术复杂度类，如GapNC 1和GapL的结构。更确切地说，我们应用形式的幂级数运算的反演和根提取这些复杂性类。我们定义了一个计数版本的Kleene封闭，并表明它是密切相关的反演和根提取GapNC 1和GapL。我们证明了Kleene闭包、求逆和根抽取在以下意义上都是硬操作：在AC 0中存在一种语言，对于该语言，求逆和根抽取是GapL-完全的，Kleene闭包是NLOG-完全的，并且存在一个有限集，对于该有限集，求逆和根抽取是GapNC 1-完全的，Kleene闭包是NC 1-完全的.后一个结果提出了对有限语言进行分类的问题，以便它们的逆属于GapNC 1的有趣子类，例如GapAC 0。我们开始在这个方向上的工作进行分类的复杂性的Kleene封闭的有限语言。我们制定的问题在有限的幺半群，并将其复杂性的内部结构的幺半群。本文的一些结果显示的性质的复杂性类是有趣的独立于正式的幂级数的考虑，包括一些有用的封闭性和完整的问题GapL。
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.