On the spectra of universal relational sentences

Abstract

The problem of deciding whether two universal relational sentences have the same spectrum is solvable by an algorithm whose run time is bounded by a linear stack of 2s, but not by an algorithm whose run time is bounded by a fixed stack of 2s. © 1984 Academic Press, Inc.