2004) and also to compute G−E for some free ET E, where |G| = def |L| + |H| + |E| + |D|.
sAT (as well as each branch of ENUM) runs in O(|L||G|) time, meaning that the worst-case time-complexity of sAT (and each branch of ENUM) is quadratic in the size of G. This result is for weakly normal hypernets-that is, when there are no label-tohole constraints.