Campus Units
Mathematics, Computer Science
Document Type
Article
Publication Version
Published Version
Publication Date
2000
Journal or Book Title
SIAM Journal on Computing
Volume
30
Issue
2
First Page
359
Last Page
382
DOI
10.1137/S0097539798345944
Abstract
In this paper we consider the complexity of several problems involving finite algebraic structures. Given finite algebras A and B, these problems ask the following. (1) Do A and B satisfy precisely the same identities? (2) Do they satisfy the same quasi-identities? (3) Do A and B have the same set of term operations?
In addition to the general case in which we allow arbitrary (finite) algebras, we consider each of these problems under the restrictions that all operations are unary and that A and B have cardinality two. We briefly discuss the relationship of these problems to algebraic specification theory.
Copyright Owner
Society for Industrial and Applied Mathematics
Copyright Date
2000
Language
en
File Format
application/pdf
Recommended Citation
Bergman, Clifford and Slutzki, Giora, "Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras" (2000). Mathematics Publications. 3.
https://lib.dr.iastate.edu/math_pubs/3
Comments
This article is published as Bergman, Clifford, and Giora Slutzki. "Complexity of some problems concerning varieties and quasi-varieties of algebras." SIAM Journal on Computing 30, no. 2 (2000): 359-382. DOI: 10.1137/S0097539798345944. Posted with permission.