Volume: 17, Issue: 8(2007)
pp. 1635-1666 DOI: 10.1142/S0218196707004335
|
|
Abstract |
Full Text (PDF, 398KB)
|
References
|
 |
| Title: |
COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS |
| Author(s): |
MARCIN KOZIK
Theoretical Computer Science Department, Jagiellonian University, Kraków, Poland
|
| History: |
Received 5 July 2005
Revised 18 October 2006
|
| Abstract: |
In this paper we produce a finite algebra which generates a variety with a PSPACE-complete membership problem. We produce another finite algebra with a γ function that grows exponentially. The results are obtained via a modification of a construction of the algebra A(T) that was introduced by McKenzie in 1996. |
| Keywords: |
Membership problem; finitely generated varieties; computational complexity
|
