  First-order logic is a natural way of expressing the properties of
computation, traditionally used in various program logics for expressing the
correctness properties and certificates. Subsequently, modern methods in the
automated inference of program invariants progress towards the construction of
first-order definable invariants. Although the first-order representations are
very expressive for some theories, they fail to express many interesting
properties of algebraic data types (ADTs).
  Thus we propose to represent program invariants regularly with tree automata.
We show how to automatically infer such regular invariants of ADT-manipulating
programs using finite model finders. We have implemented our approach and
evaluated it against the state-of-art engines for the invariant inference in
first-order logic for ADT-manipulating programs. Our evaluation shows that
automata-based representation of invariants is more practical than the one
based on first-order logic since invariants are capable of expressing more
complex properties of the computation and their automatic construction is less
expensive.
