Computational complexity questions related to finite monoids and semigroups
Computational complexity questions related to finite monoids and semigroups
复制标题
与有限幺半群和半群相关的计算复杂性问题
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Pascal Tesson
中科院分区：
文献类型：
--
作者：
D. Thérien;Pascal Tesson
在这篇论文中，我们解决了一些问题有关的计算能力的monoid和半群的机器和计算复杂性的问题，其难度是参数化的基础半群或monoid，并发现这两个轴的研究深深交织在一起。
我们首先考虑D. Barrington和D. Therien [BT88]并着手回答两个基本问题：哪些幺半群足够丰富，可以通过任意长度的程序识别任意语言，以及哪些幺半群非常弱，以至于任何程序都有多项式长度的等价物？我们发现的证据表明，这两个概念是双重的，特别是证明，在DS的每一个幺半群恰好有这两个属性之一。我们还证明，某些“弱”品种的monoid，程序只能识别这些语言与“中性字母”，可以通过态射识别该品种。
然后，我们建立了一个代数的方法来通信的复杂性，一个领域，这一直是非常重要的研究小的复杂性类。我们证明了在这个模型中，每个幺半群的通信复杂度为O（1），T（logn）或T（n）.我们得到类似的分类有限monoid的概率，同时，概率同时和MOD p-计数变量的这种两方模型的通信复杂性，从而表征的通信复杂性（在最坏情况下的分区意义上）的每一个正规语言在这五个模型。在此基础上，我们研究了经典通信模型的Chandra-Furst-Lipton多方扩展中的同样问题，并描述了具有有界3方通信复杂性和有界k方通信复杂性的幺半群的种类.我们还展示了如何使用这些界限来建立计算限制的程序在某些类的幺半群。
最后，我们考虑了测试的计算复杂性，如果一个方程或方程组在一些固定的有限幺半群（或半群）有一个解决方案。（摘要由UMI缩短。）
In this thesis, we address a number of issues pertaining to the computational power of monoids and semigroups as machines and to the computational complexity of problems whose difficulty is parametrized by an underlying semigroup or monoid and find that these two axes of research are deeply intertwined.
We first consider the “program over monoid” model of D. Barrington and D. Therien [BT88] and set out to answer two fundamental questions: which monoids are rich enough to recognize arbitrary languages via programs of arbitrary length, and which monoids are so weak that any program over them has an equivalent of polynomial length? We find evidence that the two notions are dual and in particular prove that every monoid in DS has exactly one of these two properties. We also prove that for certain “weak” varieties of monoids, programs can only recognize those languages with a “neutral letter” that can be recognized via morphisms over that variety.
We then build an algebraic approach to communication complexity, a field which has been of great importance in the study of small complexity classes. We prove that every monoid has communication complexity O(1), T(log n) or T(n) in this model. We obtain similar classifications for the communication complexity of finite monoids in the probabilistic, simultaneous, probabilistic simultaneous and MOD p-counting variants of this two-party model and thus characterize the communication complexity (in a worst-case partition sense) of every regular language in these five models. Furthermore, we study the same questions in the Chandra-Furst-Lipton multiparty extension of the classical communication model and describe the variety of monoids which have bounded 3-party communication complexity and bounded k-party communication complexity for some k. We also show how these bounds can be used to establish computational limitations of programs over certain classes of monoids.
Finally, we consider the computational complexity of testing if an equation or a system of equations over some fixed finite monoid (or semigroup) has a solution. (Abstract shortened by UMI.)