The first edition of the language defining report ignored the question of how a compiler might test for equivalence. The final Edition (1975) gave a remarkable algorithm which I describe here. It noted that it was then well known, but alas not well enough known. There was no attribution as to source.
The problem arises in asking whether two structures are equivalent. Normally you require that the respective structure fields be equivalent, but that rule leads to the useless observation that zot and zat are equivalent just in case they are equivalent. The provided decision procedure allows, while testing the individual fields in structures A and B, one to assume that A is equivalent to B. This is just short of the familiar bogus logic of saying that it OK to assume X during the proof of X. It is also a bit like valid mathematical recursion proofs. There may be several such recursion hypotheses in effect as the tree of possible equivalences (or discrepancies) is traversed.
This equivalence concept may be described as requiring that the infinite trees produced by such definitions be identical. Such trees do not include type names, but do, in the case of Algol68, include field names.
I don't know the worst case performance of this algorithm. I wrote it and watched it run and I could not find cases that make it run slowly. Here is the algorithm applied to testing Scheme values that are infinite due to loops in the pointer structures.
Algol68 requires a pointer in any declaration loop thus disallowing types such as:
typedef struct{float a; Zot g;} Zot;