Complexity of Some Problems Concerning Varieties and Quasi-Varieties of Algebras

Date
2000-01-01
Authors
Bergman, Clifford
Slutzki, Giora
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Computer Science
Organizational Unit
Mathematics
Organizational Unit
Journal Issue
Series
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.

Description

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.

Keywords
variety, quasi-variety, clone, term-equivalence, computational complexity, logarithmic space, polynomial space, hyperexponential time, nondeterminism
Citation
DOI
Collections