Logic in Computer Science (LICS 2000)

Paper: Computational Complexity of Some Problems Involving Congruences on Algebras (at LICS 2000)

Authors: Clifford Bergman Giora Slutzki

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.

BibTeX

  @InProceedings{BergmanSlutzki-ComputationalComple,
    author = 	 {Clifford Bergman and Giora Slutzki},
    title = 	 {Computational Complexity of Some Problems Involving Congruences on Algebras},
    booktitle =  {Proceedings of the Fifteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2000},
    year =	 2000,
    editor =	 {Martin Abadi},
    month =	 {June}, 
    pages =      {168--174},
    location =   {Santa Barbara, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }