Complexity of some problems concerning varieties and quasi-varieties of algebras. (English) Zbl 0963.68077
Summary: 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.
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.
MSC:
68Q25 | Analysis of algorithms and problem complexity |
08C15 | Quasivarieties |
08A40 | Operations and polynomials in algebraic structures, primal algebras |
68Q65 | Abstract data types; algebraic specification |
08B15 | Lattices of varieties |