Constructing infinite models represented by tree automata

摘要

We propose a method to use finite model builders in order to construct infinite models of first-order formulae. The constructed models are Herbrand interpretations, in which the interpretation of the predicate symbols is specified by tree tuple automata (Comon et al. 1997). Our approach is based on formula transformation: a formula Φ is transformed into a formula Δ(Φ) s.t. Φ has a model representable by a term tuple automaton iff Δ(Φ) has a finite model. This paper is an extended version of Peltier (2008).