  First-order logic is a natural way of expressing properties of computation.
It is traditionally used in various program logics for expressing the
correctness properties and certificates. Although such representations are
expressive for some theories, they fail to express many interesting properties
of algebraic data types (ADTs). In this paper, we explore three different
approaches to represent program invariants of ADT-manipulating programs: tree
automata, and first-order formulas with or without size constraints. We compare
the expressive power of these representations and prove the negative
definability of both first-order representations using the pumping lemmas. We
present an approach to automatically infer program invariants of
ADT-manipulating programs by a reduction to a finite model finder. The
implementation called RInGen has been evaluated against state-of-the-art
invariant synthesizers and has been experimentally shown to be competitive. In
particular, program invariants represented by automata are capable of
expressing more complex properties of computation and their automatic
construction is often less expensive.
