This applet can calculate or estimate the critical relations of small arities of a finite relational structure. The generator relations must be entered, and then the algorithm iteratively generates relations in the relational clone using products, projections and intersections, finds the meet-irreducible relations and determines which of those are directly indecomposable.
It is not practical to really find all relations of some arity in the relational clone, because some relations might be generated only through some very large arity intermediate relations. Instead, we maintain the list of possibly irreducible relations of a given arity n (starting from the generators) expand them to n+1 arity relations in all possible ways, compute all possible intersections and project it back to the first n coordinate. So we only calculate those relations that can iteratively be obtained by this process (by adding one or more extra coordinates). Actually, we do not calculate all intersections either, but encode an arbitrary intersection of these n+1 arity relations as a SAT problem and use a SAT solver to find such intersection whose n arity projection is not already represented as the intersection our candidate critical relations.
You have to type in your input into the following field. Elements are numbered from 0 till size-1, using the letter a for 10, b for 11, etc. A tuple is a sequence of elements (without separation), and a relation is a sequence of tuples separated by spaces. First you have to specify the size of your relational structure, then the arity of the meet irreducible relations you want to find (these will be directly decomposed into critical relations). Then you specify the list of relations in the structure, one per line. You can change the extra number of coordinates that is used in the generation process from the default value of 1. The format of the input is the following:
size <number> rel <relation> ... rel <relation> [ idempotent ] arity <number> extra <number>
For example, to find the 4-ary critical relations of the 4-element crown poset, use the following script:
size 4 rel 00 11 22 33 02 03 12 13 arity 4