Differences
This shows you the differences between two versions of the page.
finite_ordered_semigroups [2010/08/18 23:51] jipsen |
finite_ordered_semigroups [2010/08/21 01:03] (current) jipsen |
||
---|---|---|---|
Line 1: | Line 1: | ||
=====Finite nonisomorphic ordered semigroups===== | =====Finite nonisomorphic ordered semigroups===== | ||
<html> | <html> | ||
- | <style> | + | <div id="insert"></div> |
- | td {padding-left:3px;padding-right:3px;} | + | <script src="http://math.chapman.edu/~jipsen/structures/ua.js"></script> |
- | th {background-color:#f0f0f0;font-weight:normal;padding-left:3px;padding-right:3px;} | + | <script>init("OSgrp",4,{associative:true,ordered:true})</script> |
- | table {border-collapse:collapse;line-height:80%;} | + | |
- | </style> | + | |
- | Format as <select id="format" onchange="displayAlgebras(filtlist)"> | + | |
- | <option value="table" selected>Table</option> | + | |
- | <option value="html">HTML</option> | + | |
- | <option value="text">Text</option> | + | |
- | </select> | + | |
- | | Filter by | + | |
- | <b>Is subdirectly irreducible</b><input type="checkbox" name="si" id="siyes" onclick="document.getElementById('sino').checked=false;update()">yes | + | |
- | <input type="checkbox" name="si" id="sino" onclick="document.getElementById('siyes').checked=false;update()">no | + | |
- | <b>Is simple</b><input type="checkbox" name="simple" id="simpleyes" onclick="document.getElementById('simpleno').checked=false;update()">yes | + | |
- | <input type="checkbox" name="simple" id="simpleno" onclick="document.getElementById('simpleyes').checked=false;update()">no | | + | |
- | Find algebras of size <input type="text" id="minsize" size="1" maxlength="2" value="1"> to <input type="text" id="maxsize" size="1" maxlength="2" value="4"><input type="button" value="Search" onclick="searchAlgebras()"> | Counts: <span id="counts"></span> | + | |
- | + | ||
- | <div id="algebras"></div> | + | |
- | + | ||
- | <script> | + | |
- | function algebraToString(a,k,n) { | + | |
- | if (format=="html"){ | + | |
- | var st="<div style=\"display:inline-block;border: 1px darkgray solid;\"><sup>"+n+"</sup>"+"<b>S</b><sub>"+a.length+","+k+"</sub><br>"; | + | |
- | for (var i=0; i<a.length; i++) { | + | |
- | for (var j=0; j<a.length; j++) st = st+a[i][j]+(j==a.length-1?"":" "); | + | |
- | st = st+"<br>"; | + | |
- | } | + | |
- | st = st+"</div> "; | + | |
- | }else if (format=="table"){ | + | |
- | var st="<table style=\"display:inline-block;border: 1px darkgray solid;\"><tr><td colspan=\""+(a.length+1)+"\"><sup>"+n+"</sup>"+"<b>S</b><sub>"+a.length+","+k+"</sub></td></tr><tr><th>·</th>"; | + | |
- | for (var i=0; i<a.length; i++) st += "<th>"+i+"</th>"; | + | |
- | st += "</tr>"; | + | |
- | for (var i=0; i<a.length; i++) { | + | |
- | st += "<tr><th>"+i+"</th>"; | + | |
- | for (var j=0; j<a.length; j++) | + | |
- | st = st+"<td>"+a[i][j]+"</td>"; | + | |
- | st = st+"</tr>"; | + | |
- | } | + | |
- | st = st+"</table> "; | + | |
- | }else if (format=="text"){ | + | |
- | var st="{n:"+n+", name:\""+classname+"_{"+a.length+","+k+"}\", size:"+a.length+", "; | + | |
- | st=st+"num:"+k+", op:{\"cdot\":[\n"; | + | |
- | for (var i=0; i<a.length; i++) { | + | |
- | st = st+"["; | + | |
- | for (var j=0; j<a.length; j++) | + | |
- | st = st+a[i][j]+(j==a.length-1?"":","); | + | |
- | st = st+"]"+(i==a.length-1?"]}},":",")+"\n"; | + | |
- | } | + | |
- | st = st+"\n"; | + | |
- | } | + | |
- | return st; | + | |
- | } | + | |
- | 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 z=x+1; z<y; z++) | + | |
- | if (rel[x][z]==0 || rel[y][z]==0) | + | |
- | return false; //not order convex | + | |
- | for (var r in A.op) { | + | |
- | op = A.op[r]; | + | |
- | 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 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+")",*/ rel:{}}; | + | |
- | var cl = congruences(A); | + | |
- | conA.size = cl.length; | + | |
- | conA.eltname = new Array(conA.size); | + | |
- | for (var i=0; i<conA.size; i++) { | + | |
- | conA.eltname[i] = cong2part(cl[i]).join(" | "); | + | |
- | } | + | |
- | conA.rel.uc = leq2uppercovers(conLatleq(cl)); | + | |
- | return conA; | + | |
- | } | + | |
- | function isSimple(A) { | + | |
- | return congruences(A).length==2; | + | |
- | } | + | |
- | function isSI(A) { | + | |
- | var conA = conLat(A); | + | |
- | return conA.rel.uc[0].length==1; | + | |
- | } | + | |
- | /////////////////////////////////////////////////////////////////////// | + | |
- | classname="OSgrp"; | + | |
- | counts=[]; | + | |
- | filtcounts=[]; | + | |
- | function initializeAlgebra(n) { // finite groupoid with n elements, {0,1,...,n-1} | + | |
- | var alg = new Array(n); | + | |
- | for (var i=0; i<n; i++) { | + | |
- | alg[i] = new Array(n); | + | |
- | for (var j=0; j<n; j++) | + | |
- | alg[i][j] = n; // all elements undefined (=n) | + | |
- | } | + | |
- | return alg; | + | |
- | } | + | |
- | function checkAxioms(a) { | + | |
- | var n,ok,x,y,z,xy,xyz; | + | |
- | n = a.length; | + | |
- | ok = true; | + | |
- | for (x=0; ok && x<n; x++) { | + | |
- | for (y=0; ok && y<n; y++) { | + | |
- | xy=a[x][y]; | + | |
- | if (xy<n) { | + | |
- | // ok = !(a[y][x]<n && xy!=a[y][x]); // check commutativity | + | |
- | if (ok) { | + | |
- | for (z=0; ok && z<n; z++) { | + | |
- | xyz = a[xy][z]; | + | |
- | if (xyz<n) // check associativity | + | |
- | ok = !(a[y][z]<n && | + | |
- | a[x][a[y][z]]<n && xyz!=a[x][a[y][z]]); | + | |
- | } | + | |
- | } | + | |
- | } | + | |
- | } | + | |
- | } | + | |
- | return ok; | + | |
- | } | + | |
- | function completeAlgebra(alg,i,j) { | + | |
- | // find next i,j where alg[i][j]=n=undefined; for each val=0..n-1 | + | |
- | // set alg[i][j]=val, check axioms and permutations | + | |
- | // if ok, call completeAlg(alg,i,j+1) then restore and return | + | |
- | var ok = true; | + | |
- | var n = alg.length; | + | |
- | while (ok && i<n) { | + | |
- | while (j<n && alg[i][j]<n) j++; | + | |
- | if (j>=n) { | + | |
- | j = 0; | + | |
- | i++; | + | |
- | } else ok = false; | + | |
- | } | + | |
- | if (ok) { | + | |
- | counts[alg.length-1]++; | + | |
- | alglist[alglist.length] = {size:alg.length,op:{cdot:copyOf(alg)},num:counts[alg.length-1]}; | + | |
- | } else { | + | |
- | var start = 0; | + | |
- | if (i>0) start = alg[i-1][j]; | + | |
- | if (j>0 && alg[i][j-1]>start) start = alg[i][j-1]; | + | |
- | for (var val=start; val<n; val++) { | + | |
- | alg[i][j] = val; | + | |
- | ok = checkAxioms(alg); | + | |
- | // if (ok) ok = checkPermutations(alg); | + | |
- | if (ok) completeAlgebra(alg,i,j+1); | + | |
- | alg[i][j] = n; | + | |
- | } | + | |
- | } | + | |
- | } | + | |
- | function findAlgebras(size) { | + | |
- | counts[size-1]=0; | + | |
- | alg = initializeAlgebra(size); | + | |
- | completeAlgebra(alg,0,0); | + | |
- | } | + | |
- | function findAlgebrasRange(minsize,maxsize) { | + | |
- | alglist = []; | + | |
- | for (var i=minsize; i<=maxsize; i++) | + | |
- | findAlgebras(i); | + | |
- | } | + | |
- | function update(){ | + | |
- | findAlgebrasRange(eval(document.getElementById('minsize').value), eval(document.getElementById('maxsize').value)); | + | |
- | } | + | |
- | function filterAlgebras(As){ | + | |
- | var Bs = []; | + | |
- | for (var i=0; i<As[As.length-1].size; i++) filtcounts[i] = 0; | + | |
- | simpleyes = document.getElementById("simpleyes").checked; | + | |
- | simpleno = document.getElementById("simpleno").checked; | + | |
- | siyes = document.getElementById("siyes").checked; | + | |
- | sino = document.getElementById("sino").checked; | + | |
- | for (var i=0; i<As.length; i++) { | + | |
- | var add = (!simpleyes||!simpleno) && (!siyes||!sino); | + | |
- | if (add && (simpleyes||simpleno)) { | + | |
- | var simple = isSimple(As[i]); | + | |
- | add = simpleyes && simple || simpleno && !simple; | + | |
- | } | + | |
- | if (add && (siyes||sino)) { | + | |
- | var si = isSI(As[i]); | + | |
- | add = siyes && si || sino && !si; | + | |
- | } | + | |
- | if (add) { | + | |
- | Bs[Bs.length] = As[i]; | + | |
- | filtcounts[As[i].size-1]++; | + | |
- | } | + | |
- | } | + | |
- | filtlist = Bs; | + | |
- | displayAlgebras(Bs); | + | |
- | } | + | |
- | function displayAlgebras(As){ | + | |
- | format = document.getElementById("format").value; | + | |
- | algstr=(format=="text"?classname+"=[\n":""); | + | |
- | for (var i=0; i<As.length; i++) | + | |
- | algstr += algebraToString(As[i].op.cdot,As[i].num,i); | + | |
- | document.getElementById("algebras").innerHTML=(format=="text"?"<textarea rows=\"35\">"+algstr.slice(0,algstr.length-3)+"];\n</textarea>":algstr); | + | |
- | document.getElementById("counts").innerHTML="<a href=\"http://www.research.att.com/~njas/sequences/?q="+filtcounts.join(",+")+"&sort=0&fmt=0&language=english&go=Search\"><u><b>"+filtcounts.join(", ")+"</b></u></a>"; | + | |
- | } | + | |
- | function searchAlgebras(){ | + | |
- | findAlgebrasRange(eval(document.getElementById('minsize').value), eval(document.getElementById('maxsize').value)); | + | |
- | filterAlgebras(alglist); | + | |
- | } | + | |
- | function update(){ | + | |
- | filterAlgebras(alglist); | + | |
- | } | + | |
- | searchAlgebras(); | + | |
- | </script> | + | |
</html> | </html> |
Trace: