Finite Monoids: From Word to Circuit Evaluation
| العنوان: | Finite Monoids: From Word to Circuit Evaluation |
|---|---|
| المؤلفون: | Pierre Péladeau, Pierre McKenzie, Martin Beaudry, Denis Thérien |
| المصدر: | SIAM Journal on Computing. 26:138-152 |
| بيانات النشر: | Society for Industrial & Applied Mathematics (SIAM), 1997. |
| سنة النشر: | 1997 |
| مصطلحات موضوعية: | Combinatorics, Monoid, Nilpotent, General Computer Science, Closure (mathematics), Mathematics::Category Theory, General Mathematics, Complexity class, Structure (category theory), Cyclic group, Prime (order theory), Word (group theory), Mathematics |
| الوصف: | The problem of evaluating a circuit whose wires carry values from a finite monoid $M$ and whose gates perform the monoid operation provides a meaningful generalization to the well-studied problem of evaluating a word over $M$. Evaluating words over monoids is closely tied to the fine structure of the complexity class $NC^1$, and in this paper analogous ties between evaluating circuits over monoids and the structure of the complexity class $P$ are exhibited. It is shown that circuit evaluation in the case of any nonsolvable monoid is $P$ complete, while circuits over solvable monoids can be evaluated in $DET \subseteq NC^2$. Then the case of aperiodic monoids is completely elucidated: their circuit evaluation problems are either in $AC^0$ or $L$- or $NL$-complete, depending on the precise algebraic properties of the monoids. Finally, it is shown that the evaluation of circuits over the cyclic group ${\Bbb Z}_q$ for fixed $q \geq 2$ is complete for the logspace counting class $co$-$MOD_qL$, that the problem for $p$-groups ($p$ a prime) is complete for $MOD_pL$, and that the more general case of nilpotent groups of exponent $q$ belongs to the Boolean closure of $MOD_qL$. |
| تدمد: | 1095-7111 0097-5397 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::3fa0a07854d28e5fdea2d73d2c307b9d https://doi.org/10.1137/s0097539793249530 |
| رقم الأكسشن: | edsair.doi...........3fa0a07854d28e5fdea2d73d2c307b9d |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 10957111 00975397 |
|---|