Effective subdirect decomposition: A case study (Q1193629)

Let \(A\) be an algebra. A family \(\mathcal F\) of congruences on \(A\) is called an abstract subdirect decomposition of \(A\) if \(A/\sigma\) is a subdirectly irreducible algebra for every \(\sigma\in{\mathcal F}\), and for every pair \(a,b\in A\) of distinct elements there exists \(\sigma\in{\mathcal F}\) with \((a,b)\not\in\sigma\). By an explicit subdirect decomposition of \(A\) is meant an explicit list \(\mathcal G\) of quotient algebras of \(A\) which are subdirectly irreducible together with an injective homomorphism \(\varphi: A\to\Pi\{B; B\in{\mathcal G}\}\). A pseudocomplemented semilattice is an algebra \((A;\land,*,0)\), where \((A;\land)\) is a meet semilattice with the smallest element 0, and \(*\) is a unary operation such that \(a^*\) is the largest element satisfying \(a^*\land a=0\). A pseudocomplemented lattice is an algebra \((A;\lor,\land,*,0)\) provided that \((A;\lor,\land)\) is a lattice and \((A;\land,*,0)\) is a pseudocomplemented semilattice. Given a finite pseudocomplemented semilattice on \(n\) elements, algorithms are presented for: 1) an abstract subdirect decomposition in \(O(n^ 2)\) time, and 2) an explicit subdirect decomposition in \(O(n^ 3)\) time. Given a finite pseudocomplemented lattice on \(n\) elements, an algorithm is presented for an abstract subdirect decomposition in \(O(n^ 3\log(n))\) time.