Name
Abstract | ||
|---|---|---|
Given tuples a(1), . . . , a(k) and b in A(n) for some algebraic structure A, the subpower membership problem asks whether b is in the subalgebra of A(n) that is generated by a(1), . . . , a(k). For A a finite group, there is a folklore algorithm which decides this problem in time polynomial in n and k. We show that the subpower membership problem for any finite Mal'cev algebra is in NP and give a polynomial time algorithm for any finite Mal'cev algebra with finite signature and prime power size that has a nilpotent reduct. In particular, this yields a polynomial algorithm for finite rings, vector spaces, algebras over fields, Lie rings and for nilpotent loops of prime power order. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1142/S0218196712500750 | INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION |
Keywords | Field | DocType |
Subalgebras of powers, membership test, generators, partial functions, interpolation, Mal'cev algebras | Subalgebra,Discrete mathematics,Vector space,Reduct,Polynomial,Algebra,Algebraic structure,Finite group,Prime power,Mathematics,Nilpotent | Journal |
Volume | Issue | ISSN |
22 | 7 | 0218-1967 |
Citations | PageRank | References |
4 | 0.62 | 2 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Mayr | 1 | 5 | 3.34 |