  We give a complete classification of finitely generated virtually free groups
up to $\forall\exists$-elementary equivalence. As a corollary, we give an
algorithm that takes as input two finite presentations of virtually free
groups, and decides whether these groups have the same $\forall\exists$-theory
or not.
