Campus Units

Computer Science, Mathematics

Document Type

Article

Publication Version

Accepted Manuscript

Publication Date

1-6-2002

Journal or Book Title

Theoretical Computer Science

Volume

270

Issue

1-2

First Page

591

Last Page

608

DOI

10.1016/S0304-3975(01)00009-3

Abstract

We prove that several problems concerning congruences on algebras are complete for nondeterministic log-space. These problems are: determining the congruence on a given algebra generated by a set of pairs, and determining whether a given algebra is simple or subdirectly irreducible. We also consider the problem of determining the smallest fully invariant congruence on a given algebra containing a given set of pairs. We prove that this problem is complete for nondeterministic polynomial time.

Comments

This is a manuscript of an article published as Bergman, Clifford, and Giora Slutzki. "Computational complexity of some problems involving congruences on algebras." Theoretical Computer Science 270, no. 1-2 (2002): 591-608. doi: 10.1016/S0304-3975(01)00009-3. Posted with permission.

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Copyright Owner

Elsevier Science B.V.

Language

en

File Format

application/pdf

Published Version

Share

COinS