Calculate congruence lattices of small algebras

Calculate the congruence lattice of a finite algebra in JavaScript

2003 May 28 jipsen@chapman.edu

<script> function checkRelation(A,rel) {//rel is a partial binary relation //Check that rel is transitive and compatible with the operations of A var op; var n = A.size; for (var x=0; x<n; x++) for (var y=0; y<n; y++) if (rel[x][y]==1 && x!=y) { for (var z=x+1; z<n; z++) if (rel[y][z]==1) if (rel[x][z]==0) return false; //not transitive for (var r=0; r<A.operation.length; r++) { op = A.operation[r].value; if (op.length!=null) if (op[0].length==null) { if (rel[op[x]][op[y]]==0) return false; } else for (var z=0; z<n; z++) { if (rel[op[x][z]][op[y][z]]==0) return false; if (rel[op[z][x]][op[z][y]]==0) return false; } } } return true; }

function copyOf(arr) { var a = new Array(arr.length); for (var i=0; i<arr.length; i++) { a[i] = new Array(arr[i].length); for (var j=0; j<arr[i].length; j++) a[i][j] = arr[i][j]; } return a; }

function completeRelation(A,rel,i,j) { // find next i,j where rel[i][j]=2=undefined; for each val=0 or 1 // set rel[i][j]=val, check transitivity and compatibility // restore and return if no completetion, // else call completeRelation(rel,i,j+1) var ok = true; while (ok && i<rel.length) { while (j<rel.length && rel[i][j]!=2) j++; if (j>=rel.length) { j=0; i++; } else ok = false; } if (ok) congl[congl.length] = copyOf(rel); else for (var val=0; val<2; val++){ rel[i][j] = val; rel[j][i] = val; ok = checkRelation(A,rel); if (ok) completeRelation(A,rel,i,j+1); rel[i][j] = 2; rel[j][i] = 2; } }

function congruences(A) { // A is a finite algebra (JavaScript object) congl = []; var rel = new Array(A.size); for (var i=0; i<A.size; i++) { rel[i] = new Array(A.size); for (var j=0; j<A.size; j++) if (i!=j) rel[i][j] = 2; else rel[i][j]=1; } completeRelation(A,rel,0,0); return congl; }

function isTransitiveRel(rel) { var n = rel.length; for (var x=0; x<n; x++) for (var y=0; y<n; y++) if (rel[x][y]==1 && x!=y) for (var z=0; z<n; z++) if (rel[y][z]==1) if (rel[x][z]==0) return false; //not transitive return true; }

function isSubrelation(R,S) { //assumes symmetry of relations for (var i=0; i<R.length; i++) for (var j=i+1; j<R.length; j++) if (R[i][j]>S[i][j]) return false; return true; }

function conLatleq(cong) { //input list of 0-1-relations var leq = new Array(cong.length); for (var i=0; i<cong.length; i++) { leq[i] = new Array(cong.length); leq[i][i] = true; for (var j=0; j<cong.length; j++) if (i!=j) leq[i][j] = isSubrelation(cong[i],cong[j]); } return leq; }

function leq2uppercovers(rel) { var n = rel.length; var uc = new Array(n); for (var i=0; i<n; i++) { uc[i] = []; for (var j=0; j<n; j++) if (rel[i][j] && i!=j) { for (var k=0; k<n && !(rel[i][k] && i!=k && rel[k][j] && k!=j); k++); if (k==n) uc[i][uc[i].length] = j; } } return uc; }

function congblock(co,i) { var block = []; for (var j=0; j<co.length; j++) if (co[i][j]==1) block[block.length] = j; return block; }

function cong2part(co) { var part = []; var flag = new Array(co.length); for (var i=0; i<co.length; i++) if (flag[i]==null) { cb = congblock(co,i); for (var j=0; j<cb.length; j++) flag[cb[j]]=true; part[part.length] = cb; } return part; }

function conLat(A) { var conA = {name:"Con("+A.name+")", relation:[]}; var cl = congruences(A); conA.size = cl.length; conA.element = new Array(conA.size); for (var i=0; i<conA.size; i++) { conA.element[i]={id:i}; conA.element[i].value = cong2part(cl[i]).join(" | "); } conA.relation[0] = {name:"uppercovers", arity:2, type:"list"}; conA.relation[0].value = leq2uppercovers(conLatleq(cl)); return conA; }

function readStructure(st) { // A structure is an object {name:"String", size:Number, element:Array, // operation:Array, relation:Array} var A = {}; A.name = /name=\"(.*?)\"/.exec(st)[1]; A.size = parseInt(/size=\"(.*?)\"/.exec(st)[1]); var elementRe=/id=\"(.*?)\"/g; var arr=elementRe.exec(st); A.element = []; var i = 0; while (arr!=null) { A.element[i] = {}; A.element[i].id = arr[1]; i++; arr=elementRe.exec(st); } var oparr=st.split("<operation").slice(1); var row = []; A.operation = []; for (var k=0; k<oparr.length; k++) { opname = /name=\"(.*?)\"/.exec(oparr[k])[1]; A.operation[k] = {name:opname}; A.operation[k].symbol = /symbol=\"(.*?)\"/.exec(oparr[k])[1]; A.operation[k].arity = /arity=\"(.*?)\"/.exec(oparr[k])[1]; if (A.operation[k].arity == 0) A[opname] = parseInt(/>\s*(.*?)\s*<\/oper/.exec(oparr[k])[1]); else { A[opname] = new Array(A.size); var rowRe = /row.*?>\s*(.*?)\s*<\/row>/g; row = rowRe.exec(oparr[k]); i = 0; while (row!=null) { A[opname][i] = new Array(A.size); arr = row[1].split(/\s+/); for (var j=0; j<arr.length; j++) A[opname][i][j] = parseInt(arr[j]); i++; row = rowRe.exec(oparr[k]); } } if (A.operation[k].arity == 1) A[opname] = A[opname][1]; A.operation[k].value = A[opname]; } // ********* still need to read relations and comments return A; }

function structureToString(A) { var st="&lt\;structure name=\""+A.name+"\" size=\""+A.size+"\"><br>\n"; if (A.element != null) for (var i=0; i<A.size; i++) st=st+"   &lt\;element id=\""+A.element[i].id+ (A.element[i].x!=null?"\" x=\""+A.element[i].x+"\" y=\""+A.element[i].y:"")+ (A.element[i].value!=null?"\"> "+A.element[i].value+" &lt\;/element>":"\"/>")+"<br>\n"; if (A.operation != null) for (var k=0; k<A.operation.length; k++) { var ar = A.operation[k].arity; st=st+"   &lt\;operation name=\""+A.operation[k].name+"\" symbol=\""+ A.operation[k].symbol+"\" arity=\""+ar+"\" type=\"table\">"; if (ar == 0) st = st+"  "+A.operation[k].value; else for (var i=0; i<(ar==2?A.size:2); i++) { st = st+(i==0?"<br>\n":"")+"     &lt\;row id=\""+ (ar==2?(A.element!=null?A.element[i].id:i):(i==0?"s":"t"))+"\">  "; for (var j=0; j<A.size; j++) st = st+(ar==2?A.operation[k].value[i][j]:(i==0?j:A.operation[k].value[j]))+"  "; st = st+"&lt\;/row><br>\n"; } st = st+"   &lt\;/operation><br>\n"; } if (A.relation != null) for (var k=0; k<A.relation.length; k++) { var ar = A.relation[k].arity; st=st+"   &lt\;relation name=\""+A.relation[k].name+ (A.relation[k].symbol!=null?"\" symbol=\""+ A.relation[k].symbol:"")+"\" arity=\""+ar+"\" type=\"list\">"; if (ar == 1) st = st+"  "+A.relation[k].value.join(" "); else for (var i=0; i<A.size; i++) st = st+(i==0?"<br>\n":"")+"     &lt\;set id=\""+ (A.element!=null?A.element[i].id:i)+"\"> "+ A.relation[k].value[i].join(" ")+" &lt\;/set><br>\n"; st = st+"   &lt\;/relation><br>\n"; } st = st+"&lt\;/structure>\n\n<p>"; return st; }

function process(st) { var A, conA; var strString = ""; var arr=st.split("<structure"); for (var i=1; i<arr.length; i++) { A = readStructure(arr[i]); conA = conLat(A); strString = strString + structureToString(conA); } document.getElementById("output").innerHTML = strString; }

document.write( '<form>Compute congruence lattices of: (paste a list of algebras) <br>'+ '<textarea name="input" rows="10" cols="80"><structure name="Sgrp_4_4" size="4">\n\ <element id="0"/>\n\ <element id="1"/>\n\ <element id="2"/>\n\ <element id="3"/>\n\ <operation name="product" symbol="\cdot" arity="2" type="table">\n\ <row id="0"> 0 0 0 0 </row>\n\ <row id="1"> 0 0 0 0 </row>\n\ <row id="2"> 0 0 0 1 </row>\n\ <row id="3"> 0 0 1 0 </row>\n\ </operation>\n\ </structure>\n </textarea><br>'+ '<input type="button" value="Start" onClick="process(document.forms[0].input.value)"></form><p><div id="output"></div>'); </script>