Document Type

Article

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.



Comments

This article is from SIAM Journal on Computing 30 (2000): 359, doi:10.1137/S0097539798345944. Posted with permission.

Copyright Owner

Society for Industrial and Applied Mathematics

Language

en

File Format

application/pdf

Share

COinS