```// ************************************************************************** //
//                                                                            //
//    eses                   eses                                             //
//   eses                     eses                                            //
//  eses    eseses  esesese    eses   Embedded Systems Group                  //
//  ese    ese  ese ese         ese                                           //
//  ese    eseseses eseseses    ese   Department of Computer Science          //
//  eses   eses          ese   eses                                           //
//   eses   eseses  eseseses  eses    University of Kaiserslautern            //
//    eses                   eses                                             //
//                                                                            //
// ************************************************************************** //
// The following module implements Hirschberg's algorithm to compute the      //
// transitive hull of a boolean matrix in depth O(log(N)^2) using O(N^3)      //
// processors. Clearly, this algorithm is not as fast as the log(N) time      //
// version, it has the advantage that it does not require concurrent writes.  //
// Since there is in general a slowdown by O(log(N)), and since the CRCW      //
// algorithm requires time O(log(N)) by O(N) processors, this CREW algorithm  //
// is probably optimal.                                                       //
// ************************************************************************** //

[8][8] bool x;
[8][8][8] bool p;
[8][8] bool b;

function exp(nat x0, nat y0):nat {
nat h,i;
h = 1;

if(x0!=0) {
for(i=1..y0) {
h = h*x0;
}
}
return h;
}

function log(nat n) : nat {
nat h,l;
h = 1;
l = 0;
while(h<n) {
h = h*2;
l = l+1;
}

return l;
}

function TransHull_OlogNlogN(nat n, [][]bool a):nat {
nat i,j,k, step, h;
// copy matrix a to local matrix x
for(i=0..n-1){
for(j=0..n-1){
x[i][j] = a[i][j];
}
}

// multiply matrix x log(N) times with itself to obtain the transitive hull
for(step=1..log(n)){
// compute (x[i][j]) = x[i][j] | exists(k=0..N-1) x[i][k] & x[k][j]
// using a balanced tree for the disjunction with depth log(N)
for(i=0..n-1){
for(j=0..n-1){
for(k=0..n-1){
p[k][i][j] = x[i][j] | x[i][k] & x[k][j];
}
}
}
}

// for each pair (i,j), sum up p[0..N-1][i][j] in a parallel prefix tree

for(h=0..log(n)-1){
for(i=0..n-1){
for(j=0..n-1){
for(k=exp(2,h)..n-1){
p[k][i][j] = p[k][i][j] | p[k-exp(2,h)][i][j];
}
}
}
}

for(i=0..n-1){
for(j=0..n-1){
(x[i][j]) = p[n-1][i][j];
}
}

// collect the result
for(i=0..n-1)
for(j=0..n-1)
b[i][j] = x[i][j];

return 1;
}

nat t,i,j,n;
bool test_passed;
[8][8] bool a;
a[0][1] = true;
a[1][2] = true;
a[2][1] = true;
a[2][4] = true;
a[2][7] = true;
a[3][2] = true;
a[3][4] = true;
a[4][5] = true;
a[5][4] = true;
a[5][6] = true;
a[7][7] = true;
n = 8;
t = TransHull_OlogNlogN(n,a);

for(i=0..n-1){
for(j=0..n-1){
if(!((b[i][j] <->
(i==0 & (j==1 | j==2 | j==4 | j==5 | j==6 | j==7 ) |
i==1 & (j==1 | j==2 | j==4 | j==5 | j==6 | j==7 ) |
i==2 & (j==1 | j==2 | j==4 | j==5 | j==6 | j==7 ) |
i==3 & (j==1 | j==2 | j==4 | j==5 | j==6 | j==7 ) |
i==4 & (              j==4 | j==5 | j==6        ) |
i==5 & (              j==4 | j==5 | j==6        ) |
i==7 &  j==7)
)))
{
test_passed = false;
}
}
}

}

```