A polynomial time algorithm to compute the Abelian kernel of a finite monoid |
| |
| Authors: | Manuel Delgado Pierre-Cyrille Héam |
| |
| Institution: | 1. Centro de Matemática da Universidade do Porto, Rua do Campo Alegre, 687, 4169-007, Porto, Portugal
2. LIFC, Université de Franche-Comté, 16 route de Gray, 25030, Besan?on Cedex, France
|
| |
| Abstract: | The time complexity of the best previously known algorithm to compute the Abelian kernel of a finite monoid with a fixed number of generators is exponential. In this paper we use results on subgroups of the free Abelian group and constructions on labeled graphs to develop a polynomial time algorithm for this problem. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
