Typically the languages are logics in which one can express properties of models. Characterizations have been found for a wide variety of complexity classes. In spite of considerable effort, no way has been found to eliminate the need for a total order. My work on descriptive complexity focuses on finding pragmatic programming languages in which one can write all and only the programs in a given class. My work shifts the discussion from properties of finite structures to properties of finite first order terms.
Terms are in many ways more natural data structures than strings.
My basic characterization of P can be formulated directly in terms of logic programs. A logic program is a set of first order Horn clauses. Let R be a set of Horn clauses. One advantage of this characterization is that no total order need be assumed. The theorem is proved by showing that a total order on the subterms of any term can always be defined by a syntactically local rule set.